@book{choset-burgard2005principles-of-robot,
title = {Principles of Robot Motion: Theory, Algorithms, and Implementation},
author = {Choset, H. and Burgard, W. and Hutchinson, S. and Kantor, G. and Kavraki, Lydia E and Lynch, K. and Thrun, S.},
month = jun,
year = {2005},
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.},
isbn = {978-0262033275},
keyword = {fundamentals of sampling-based motion planning},
publisher = {MIT Press}
}
@book{agrawal-kavraki1998robotics-algorithmic-perspective,
title = {Robotics: The Algorithmic Perspective},
author = {Agrawal, P. K. and Kavraki, Lydia E and Mason, M.},
year = {1998},
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.},
address = {Natick MA},
isbn = {978-1568810812},
keyword = {fundamentals of sampling-based motion planning},
publisher = {AK Peters}
}
@proceedings{rss2015,
title = {Robotics Science and Systems XI},
year = {2015},
editor = {Kavraki, L. E. and Hsu, D. and Buchli, J.},
isbn = {978-0-9923747-1-6},
keyword = {other robotics},
url = {http://www.roboticsproceedings.org/rss11/index.html}
}
@proceedings{rss2014,
title = {Robotics Science and Systems X},
year = {2014},
editor = {Fox, D. and Kavraki, L. E. and Kurniawati, H.},
isbn = {978-0-9923747-0-9},
keyword = {other robotics},
url = {http://www.roboticsproceedings.org/rss10/index.html}
}
@article{kingston2022-scaling-mmp,
author = {Kingston, Zachary and Kavraki, Lydia E.},
journal = {IEEE Transactions on Robotics},
title = {Scaling Multimodal Planning: Using Experience and Informing Discrete Search},
month = feb,
year = {2023},
volume = {39},
number = {1},
pages = {128--146},
doi = {10.1109/TRO.2022.3197080},
abstract = {Robotic manipulation is inherently continuous, but typically has an underlying
discrete structure, such as if an object is grasped. Many problems like these are
multi-modal, such as pick-and-place tasks where every object grasp and placement is a mode.
Multi-modal problems require finding a sequence of transitions between modes - for example,
a particular sequence of object picks and placements. However, many multi-modal planners
fail to scale when motion planning is difficult (e.g., in clutter) or the task has a long
horizon (e.g., rearrangement). This work presents solutions for multi-modal scalability in
both these areas. For motion planning, we present an experience-based planning framework
ALEF which reuses experience from similar modes both online and from training data. For task
satisfaction, we present a layered planning approach that uses a discrete lead to bias
search towards useful mode transitions, informed by weights over mode transitions. Together,
these contributions enable multi-modal planners to tackle complex manipulation tasks that
were previously infeasible or inefficient, and provide significant improvements in scenes
with high-dimensional robots.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{guo2023-editorial,
author = {Guo, Jason L. and Kavraki, Lydia E. and Mikos, Antonios G.},
title = {Editorial for Special Issue on Machine Learning in Tissue Engineering},
journal = {Tissue Engineering Part A},
volume = {29},
number = {1--2},
pages = {1--1},
year = {2023},
doi = {10.1089/ten.tea.2022.29038.editorial},
note = {PMID: 36399697}
}
@article{verginis2022-kdf,
author = {Verginis, Christos K. and Dimarogonas, Dimos V. and Kavraki, Lydia E.},
abstract = {We integrate sampling-based planning techniques with funnel-based feedback control
to develop KDF, a new framework for solving the kinodynamic motion-planning problem via
funnel control. The considered systems evolve subject to complex, nonlinear, and uncertain
dynamics (also known as differential constraints). First, we use a geometric planner to
obtain a high-level safe path in a user-defined extended free space. Second, we develop a
low-level funnel control algorithm that guarantees safe tracking of the path by the system.
Neither the planner nor the control algorithm uses information on the underlying dynamics of
the system, which makes the proposed scheme easily distributable to a large variety of
different systems and scenarios. Intuitively, the funnel control module is able to
implicitly accommodate the dynamics of the system, allowing hence the deployment of purely
geometrical motion planners. Extensive computer simulations and hardware experiments with a
6-DOF robotic arm validate the proposed approach.},
journal = {IEEE Transactions on Robotics},
title = {KDF: Kinodynamic Motion Planning via Geometric Sampling-Based Algorithms and Funnel
Control},
year = {2023},
volume = {39},
number = {2},
pages = {978--997},
doi = {10.1109/TRO.2022.3208502}
}
@article{jackson2022-charge-interactions,
author = {Jackson, Kyle R and Antunes, Dinler A and Talukder, Amjad H and Maleki, Ariana R and Amagai, Kano and Salmon, Avery and Katailiha, Arjun S and Chiu, Yulun and Fasoulis, Romanos and Rigo, Maurício Menegatti and Abella, Jayvee R and Melendez, Brenda D and Li, Fenge and Sun, Yimo and Sonnemann, Heather M and Belousov, Vladislav and Frenkel, Felix and Justesen, Sune and Makaju, Aman and Liu, Yang and Horn, David and Lopez-Ferrer, Daniel and Huhmer, Andreas F and Hwu, Patrick and Roszik, Jason and Hawke, David and Kavraki, Lydia E and Lizée, Gregory},
title = {{Charge-based interactions through peptide position 4 drive diversity of antigen
presentation by human leukocyte antigen class I molecules}},
journal = {PNAS Nexus},
volume = {1},
number = {3},
year = {2022},
month = aug,
abstract = {Human leukocyte antigen class I (HLA-I) molecules bind and present peptides at the
cell surface to facilitate the induction of appropriate CD8+ T cell-mediated immune
responses to pathogen- and self-derived proteins. The HLA-I peptide-binding cleft contains
dominant anchor sites in the B and F pockets that interact primarily with amino acids at
peptide position 2 and the C-terminus, respectively. Nonpocket peptide–HLA interactions
also contribute to peptide binding and stability, but these secondary interactions are
thought to be unique to individual HLA allotypes or to specific peptide antigens. Here, we
show that two positively charged residues located near the top of peptide-binding cleft
facilitate interactions with negatively charged residues at position 4 of presented
peptides, which occur at elevated frequencies across most HLA-I allotypes. Loss of these
interactions was shown to impair HLA-I/peptide binding and complex stability, as
demonstrated by both in vitro and in silico experiments. Furthermore, mutation of these
Arginine-65 (R65) and/or Lysine-66 (K66) residues in HLA-A*02:01 and A*24:02 significantly
reduced HLA-I cell surface expression while also reducing the diversity of the presented
peptide repertoire by up to 5-fold. The impact of the R65 mutation demonstrates that
nonpocket HLA-I/peptide interactions can constitute anchor motifs that exert an unexpectedly
broad influence on HLA-I-mediated antigen presentation. These findings provide fundamental
insights into peptide antigen binding that could broadly inform epitope discovery in the
context of viral vaccine development and cancer immunotherapy.},
issn = {2752-6542},
doi = {10.1093/pnasnexus/pgac124},
url = {https://doi.org/10.1093/pnasnexus/pgac124}
}
@article{rigo2022-sars-arena,
title = {SARS-Arena: Sequence and Structure-Guided Selection of Conserved Peptides from
SARS-related Coronaviruses for Novel Vaccine Development},
author = {Rigo, Mauricio Menegatti and Fasoulis, Romanos and Conev, Anja and Hall-Swan, Sarah and Amaral Antunes, Dinler and Kavraki, Lydia},
journal = {Frontiers in Immunology},
month = jul,
year = {2022},
volume = {13},
doi = {10.3389/fimmu.2022.931155},
abstract = {The pandemic caused by the SARS-CoV-2 virus, the agent responsible for the COVID-19
disease, has affected millions of people worldwide. There is constant search for new
therapies to either prevent or mitigate the disease. Fortunately, we have observed the
successful development of multiple vaccines. Most of them are focused on one viral envelope
protein, the spike protein. However, such focused approaches may contribute for the rise of
new variants, fueled by the constant selection pressure on envelope proteins, and the
widespread dispersion of coronaviruses in nature. Therefore, it is important to examine
other proteins, preferentially those that are less susceptible to selection pressure, such
as the nucleocapsid (N) protein. Even though the N protein is less accessible to humoral
response, peptides from its conserved regions can be presented by class I Human Leukocyte
Antigen (HLA) molecules, eliciting an immune response mediated by T-cells. Given the
increased number of protein sequences deposited in biological databases daily and the N
protein conservation among viral strains, computational methods can be leveraged to discover
potential new targets for SARS-CoV-2 and SARS-CoV-related viruses. Here we developed
SARS-Arena, a user-friendly computational pipeline that can be used by practitioners of
different levels of expertise for novel vaccine development. SARS-Arena combines
sequence-based methods and structure-based analyses to (i) perform multiple sequence
alignment (MSA) of SARS-CoV-related N protein sequences, (ii) recover candidate peptides of
different lengths from conserved protein regions, and (iii) model the 3D structure of the
conserved peptides in the context of different HLAs. We present two main Jupyter Notebook
workflows that can help in the identification of new T-cell targets against SARS-CoV
viruses. In fact, in a cross-reactive case study, our workflows identified a conserved N
protein peptide (SPRWYFYYL) recognized by CD8+ T-cells in the context of HLA-B7+. SARS-Arena
is available at https://github.com/KavrakiLab/SARS-Arena.},
publisher = {Frontiers Media SA},
url = {https://doi.org/10.3389/fimmu.2022.931155}
}
@article{lee2022-apes,
title = {Adaptive Experience Sampling for Motion Planning using the Generator-Critic Framework},
author = {Lee, Yiyuan and Chamzas, Constantinos and E. Kavraki, Lydia},
journal = {IEEE Robotics and Automation Letters},
volume = {7},
number = {4},
month = jul,
year = {2022},
pages = {9437--9444},
doi = {10.1109/LRA.2022.3191803},
abstract = {Sampling-based motion planners are widely used for motion planning with high-dof
robots. These planners generally rely on a uniform distribution to explore the search space.
Recent work has explored learning biased sampling distributions to improve the time
efficiency of these planners. However, learning such distributions is challenging, since
there is no direct connection between the choice of distributions and the performance of the
downstream planner. To alleviate this challenge, this paper proposes APES, a framework that
learns sampling distributions optimized directly for the planner's performance. This is done
using a critic, which serves as a differentiable surrogate objective modeling the planner's
performance - thus allowing gradients to circumvent the non-differentiable planner.
Leveraging the differentiability of the critic, we train a generator, which outputs sampling
distributions optimized for the given problem instance. We evaluate APES on a series of
realistic and challenging high-dof manipulation problems in simulation. Our experimental
results demonstrate that APES can learn high-quality distributions that improve planning
performance more than other biased sampling baselines.},
keyword = {fundamentals of sampling-based motion planning},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)}
}
@article{conev2022-3phla-score,
title = {3pHLA-score improves structure-based peptide-{HLA} binding affinity prediction},
author = {Conev, Anja and Devaurs, Didier and Rigo, Mauricio M. and Antunes, Dinler A. and Kavraki, Lydia E.},
journal = {Scientific Reports},
month = jun,
year = {2022},
volume = {12},
number = {1},
doi = {10.1038/s41598-022-14526-x},
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.},
keyword = {proteins and drugs},
publisher = {Springer Science and Business Media {LLC}},
url = {https://doi.org/10.1038/s41598-022-14526-x}
}
@article{chamzas2022-learn-retrieve,
title = {Learning to Retrieve Relevant Experiences for Motion Planning},
author = {Chamzas, Constantinos and Cullen, Aedan and Shrivastava, Anshumali and E. Kavraki, Lydia},
booktitle = {2022 International Conference on Robotics and Automation (ICRA)},
month = may,
year = {2022},
pages = {7233--7240},
doi = {10.1109/ICRA46639.2022.9812076},
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.},
keyword = {fundamentals of sampling-based motion planning},
publisher = {IEEE}
}
@article{chamzas2022-motion-bench-maker,
title = {MotionBenchMaker: A Tool to Generate and Benchmark Motion Planning Datasets},
author = {Chamzas, Constantinos and Quintero-Pe{\~n}a, Carlos and Kingston, Zachary and Orthey, Andreas and Rakita, Daniel and Gleicher, Michael and Toussaint, Marc and E. Kavraki, Lydia},
journal = {IEEE Robotics and Automation Letters},
month = apr,
year = {2022},
volume = {7},
number = {2},
pages = {882--889},
doi = {10.1109/LRA.2021.3133603},
abstract = {Recently, there has been a wealth of development in motion planning for robotic
manipulationnew motion planners are continuously proposed, each with its own unique set of
strengths and weaknesses. However, evaluating these new planners is challenging, and
researchers often create their own ad-hoc problems for benchmarking, which is
time-consuming, prone to bias, and does not directly compare against other state-of-the-art
planners. We present MotionBenchMaker, an open-source tool to generate benchmarking datasets
for realistic robot manipulation problems. MotionBenchMaker is designed to be an extensible,
easy-to-use tool that allows users to both generate datasets and benchmark them by comparing
motion planning algorithms. Empirically, we show the benefit of using MotionBenchMaker as a
tool to procedurally generate datasets which helps in the fair evaluation of planners. We
also present a suite of over 40 prefabricated datasets, with 5 different commonly used
robots in 8 environments, to serve as a common ground for future motion planning research.},
issn = {2377-3766},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
url = {https://dx.doi.org/10.1109/LRA.2021.3133603}
}
@article{tarabini2022-large-scale,
title = {Large-Scale Structure-Based Screening of Potential T Cell Cross-Reactivities Involving
Peptide-Targets From BCG Vaccine and SARS-CoV-2},
author = {Tarabini, Renata Fioravanti and Rigo, Mauricio Menegatti and Faustino Fonseca, André and Rubin, Felipe and Bellé, Rafael and Kavraki, Lydia E and Ferreto, Tiago Coelho and Amaral Antunes, Dinler and de Souza, Ana Paula Duarte},
journal = {Frontiers in Immunology},
month = jan,
year = {2022},
volume = {12},
doi = {10.3389/fimmu.2021.812176},
abstract = {Although not being the first viral pandemic to affect humankind, we are now for the
first time faced with a pandemic caused by a coronavirus. The Severe Acute Respiratory
Syndrome Coronavirus 2 (SARS-CoV-2) has been responsible for the COVID-19 pandemic, which
caused more than 4.5 million deaths worldwide. Despite unprecedented efforts, with vaccines
being developed in a record time, SARS-CoV-2 continues to spread worldwide with new variants
arising in different countries. Such persistent spread is in part enabled by public
resistance to vaccination in some countries, and limited access to vaccines in other
countries. The limited vaccination coverage, the continued risk for resistant variants, and
the existence of natural reservoirs for coronaviruses, highlight the importance of
developing additional therapeutic strategies against SARS-CoV-2 and other coronaviruses. At
the beginning of the pandemic it was suggested that countries with Bacillus Calmette-Guérin
(BCG) vaccination programs could be associated with a reduced number and/or severity of
COVID-19 cases. Preliminary studies have provided evidence for this relationship and further
investigation is being conducted in ongoing clinical trials. The protection against
SARS-CoV-2 induced by BCG vaccination may be mediated by cross-reactive T cell lymphocytes,
which recognize peptides displayed by class I Human Leukocyte Antigens (HLA-I) on the
surface of infected cells. In order to identify potential targets of T cell
cross-reactivity, we implemented an in silico strategy combining sequence-based and
structure-based methods to screen over 13,5 million possible cross-reactive peptide pairs
from BCG and SARS-CoV-2. Our study produced (i) a list of immunogenic BCG-derived peptides
that may prime T cell cross-reactivity against SARS-CoV-2, (ii) a large dataset of modeled
peptide-HLA structures for the screened targets, and (iii) new computational methods for
structure-based screenings that can be used by others in future studies. Our study expands
the list of BCG peptides potentially involved in T cell cross-reactivity with
SARS-CoV-2-derived peptides, and identifies multiple high-density "neighborhoods" of
cross-reactive peptides which could be driving heterologous immunity induced by BCG
vaccination, therefore providing insights for future vaccine development efforts.},
issn = {1664-3224},
publisher = {Frontiers Media SA},
url = {http://dx.doi.org/10.3389/fimmu.2021.812176}
}
@article{chamzas2022-health-robotics,
title = {Human Health and Equity in an Age of Robotics and Intelligent Machines},
author = {Chamzas, Constantinos and Eweje, Feyisayo and Kavraki, Lydia E. and Chaikof, Elliot L.},
journal = {NAM Perspectives},
year = {2022},
doi = {https://doi.org/10.31478/202203b},
publisher = {Commentary, National Academy of Medicine},
url = {https://nam.edu/human-health-and-equity-in-an-age-of-robotics-and-intelligent-machines/}
}
@article{fasoulis2021-grlsp,
title = {Graph representation learning for structural proteomics},
author = {Fasoulis, Romanos and Paliouras, Georgios and Kavraki, Lydia E.},
journal = {Emerging Topics in Life Sciences},
month = oct,
year = {2021},
doi = {10.1042/ETLS20210225},
abstract = {The field of structural proteomics, which is focused on studying the
structure–function relationship of proteins and protein complexes, is experiencing rapid
growth. Since the early 2000s, structural databases such as the Protein Data Bank are
storing increasing amounts of protein structural data, in addition to modeled structures
becoming increasingly available. This, combined with the recent advances in graph-based
machine-learning models, enables the use of protein structural data in predictive models,
with the goal of creating tools that will advance our understanding of protein function.
Similar to using graph learning tools to molecular graphs, which currently undergo rapid
development, there is also an increasing trend in using graph learning approaches on protein
structures. In this short review paper, we survey studies that use graph learning techniques
on proteins, and examine their successes and shortcomings, while also discussing future
directions.},
issn = {2397-8554},
url = {https://doi.org/10.1042/ETLS20210225}
}
@article{wang2021-online-partial-conditional-plan-synthesis,
title = {Online Partial Conditional Plan Synthesis for POMDPs With Safe-Reachability Objectives:
Methods and Experiments},
author = {Wang, Yue and Newaz, Abdullah Al Redwan and Hernández, Juan David and Chaudhuri, Swarat and Kavraki, Lydia E.},
journal = {IEEE Transactions on Automation Science and Engineering},
month = jul,
year = {2021},
volume = {18},
pages = {932--945},
doi = {10.1109/TASE.2021.3057111},
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. In this article, we study a different formulation of
POMDPs with Boolean objectives. For robotic domains that require a correctness guarantee of
accomplishing tasks, Boolean objectives are natural formulations. We investigate the problem
of POMDPs with a common Boolean objective: safe reachability, requiring that the robot
eventually reaches a goal state with a probability above a threshold while keeping the
probability of visiting unsafe states below a different threshold. Our approach builds upon
the previous work that represents POMDPs with Boolean objectives using symbolic constraints.
We employ a satisfiability modulo theories (SMTs) solver to efficiently search for
solutions, i.e., policies or conditional plans that specify the action to take contingent on
every possible event. A full policy or conditional plan is generally expensive to compute.
To improve computational efficiency, we introduce the notion of partial conditional plans
that cover sampled events to approximate a full conditional plan. Our approach constructs a
partial conditional plan parameterized by a replanning probability. We prove that the
failure rate of the constructed partial conditional plan is bounded by the replanning
probability. Our approach allows users to specify an appropriate bound on the replanning
probability to balance efficiency and correctness. Moreover, we update this bound properly
to quickly detect whether the current partial conditional plan meets the bound and avoid
unnecessary computation. In addition, to further improve the efficiency, we cache partial
conditional plans for sampled belief states and reuse these cached plans if possible. We
validate our approach in several robotic domains. The results show that our approach
outperforms a previous policy synthesis approach for POMDPs with safe-reachability
objectives in these domains.},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)}
}
@article{pairet2021-path-planning-for-manipulation,
title = {Path Planning for Manipulation Using Experience-Driven Random Trees},
author = {Pairet, Eric and Chamzas, Constantinos and Petillot, Yvan R. and Kavraki, Lydia E.},
journal = {IEEE Robotics and Automation Letters},
month = apr,
year = {2021},
volume = {6},
number = {2},
pages = {3295--3302},
doi = {10.1109/lra.2021.3063063},
abstract = {Robotic systems may frequently come across similar manipulation planning problems
that result in similar motion plans. Instead of planning each problem from scratch, it is
preferable to leverage previously computed motion plans, i.e., experiences, to ease the
planning. Different approaches have been proposed to exploit prior information on novel task
instances. These methods, however, rely on a vast repertoire of experiences and fail when
none relates closely to the current problem. Thus, an open challenge is the ability to
generalise prior experiences to task instances that do not necessarily resemble the prior.
This work tackles the above challenge with the proposition that experiences are
"decomposable" and "malleable", i.e., parts of an experience are suitable to relevantly
explore the connectivity of the robot-task space even in non-experienced regions. Two new
planners result from this insight: experience-driven random trees (ERT) and its
bi-directional version ERTConnect. These planners adopt a tree sampling-based strategy that
incrementally extracts and modulates parts of a single path experience to compose a valid
motion plan. We demonstrate our method on task instances that significantly differ from the
prior experiences, and compare with related state-of-the-art experience-based planners.
While their repairing strategies fail to generalise priors of tens of experiences, our
planner, with a single experience, significantly outperforms them in both success rate and
planning time. Our planners are implemented and freely available in the Open Motion Planning
Library.},
issn = {2377-3774},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
url = {http://dx.doi.org/10.1109/LRA.2021.3063063}
}
@article{litsa2021-expert-opinion,
title = {Machine learning models in the prediction of drug metabolism: challenges and future
perspectives},
author = {Litsa, Eleni E. and Das, Payel and Kavraki, Lydia E.},
journal = {Expert Opinion on Drug Metabolism \& Toxicology},
year = {2021},
volume = {0},
number = {0},
pages = {1--3},
doi = {10.1080/17425255.2021.1998454},
abstract = {Metabolism can be the underlying cause of drug adverse effects and diminished
efficacy. Metabolic reactions in the human body, mediated mainly by enzymes, may transform
the administered drug into metabolites that exhibit different biological activity. As a
general rule, metabolic reactions deactivate a drug; however, off-target effects or
toxicity, resulting from the formed metabolites, cannot be excluded. On the flip side,
metabolism is necessary for the formation of the active substance in the case of prodrugs.
In scenarios where multiple drugs are co-administered, the presence of a drug may inhibit or
further induce the clearance of another setting metabolism as one of the underlying causes
of drug–drug interactions. As a result, the metabolic fate of a candidate drug needs to be
thoroughly investigated during the drug development process.},
note = {PMID: 34706606},
publisher = {Taylor \& Francis},
url = {https://doi.org/10.1080/17425255.2021.1998454}
}
@article{lewis-2021-commentary,
title = {How Should We Prepare for the Post-Pandemic World of Telehealth and Digital Medicine?},
author = {Rokosh, Rae S. and Lewis II, W. Cannon and Chaikof, Elliot L. and Kavraki, Lydia E.},
journal = {NAM Perspectives},
year = {2021},
doi = {https://doi.org/10.31478/202106a},
publisher = {Commentary, National Academy of Medicine},
url = {https://nam.edu/how-should-we-prepare-for-the-post-pandemic-world-of-telehealth-and-digital-medicine/}
}
@article{hall-swan2021-dinc-covid,
title = {DINC-COVID: A webserver for ensemble docking with flexible SARS-CoV-2 proteins},
author = {Hall-Swan, Sarah and Devaurs, Didier and Rigo, Mauricio M. and Antunes, Dinler A. and Kavraki, Lydia E. and Zanatta, Geancarlo},
journal = {Computers in Biology and Medicine},
year = {2021},
volume = {139},
pages = {104943},
doi = {https://doi.org/10.1016/j.compbiomed.2021.104943},
abstract = {An unprecedented research effort has been undertaken in response to the ongoing
COVID-19 pandemic. This has included the determination of hundreds of crystallographic
structures of SARS-CoV-2 proteins, and numerous virtual screening projects searching large
compound libraries for potential drug inhibitors. Unfortunately, these initiatives have had
very limited success in producing effective inhibitors against SARS-CoV-2 proteins. A reason
might be an often overlooked factor in these computational efforts: receptor flexibility. To
address this issue we have implemented a computational tool for ensemble docking with
SARS-CoV-2 proteins. We have extracted representative ensembles of protein conformations
from the Protein Data Bank and from in silico molecular dynamics simulations. Twelve
pre-computed ensembles of SARS-CoV-2 protein conformations have now been made available for
ensemble docking via a user-friendly webserver called DINC-COVID
(dinc-covid.kavrakilab.org). We have validated DINC-COVID using data on tested inhibitors of
two SARS-CoV-2 proteins, obtaining good correlations between docking-derived binding
energies and experimentally-determined binding affinities. Some of the best results have
been obtained on a dataset of large ligands resolved via room temperature crystallography,
and therefore capturing alternative receptor conformations. In addition, we have shown that
the ensembles available in DINC-COVID capture different ranges of receptor flexibility, and
that this diversity is useful in finding alternative binding modes of ligands. Overall, our
work highlights the importance of accounting for receptor flexibility in docking studies,
and provides a platform for the identification of new inhibitors against SARS-CoV-2
proteins.},
issn = {0010-4825},
keyword = {COVID-19, SARS-CoV-2, Molecular docking, Ensemble docking, Receptor flexibility,
Molecular dynamics},
url = {https://www.sciencedirect.com/science/article/pii/S001048252100737X}
}
@article{daniilidis2021-robotics-hellenic,
title = {Robotics in the AI era: A vision for a Hellenic Robotics Initiative},
author = {Daniilidis, Kostas and Guibas, Leonidas and Kavraki, Lydia and Koumoutsakos, Petros and Kyriakopoulos, Kostas and Lygeros, John and Pappas, George J. and Triantafyllou, Michael and Tsiotras, Panagiotis},
journal = {Foundations and Trends in Robotics},
year = {2021},
volume = {9},
number = {3},
pages = {201--265},
doi = {10.1561/2300000069},
abstract = {In January 2021, the Hellenic Institute of Advanced Study (HIAS) assembled a panel
including world leading roboticists from the Hellenic diaspora, who volunteered their
scientific expertise to provide a vision for Robotics in Greece. This monograph, entitled
"Robotics in the Artificial Intelligence (AI) era," will hopefully trigger a dialogue
towards the development of a national robotics strategy. Our vision is that Robotics in the
AI era will be an essential technology of the future for the safety and security of the
Hellenic nation, its environment and its citizens, for modernizing its economy towards
Industry 4.0, and for inspiring and educating the next generation workforce for the
challenges of the 21st century. To contribute towards making this vision a reality, after
reviewing global trends in robotics and assessing the Greek robotics ecosystem, we arrived
at the following key findings and recommendations: Firstly, we think that Greece should
develop a national Hellenic Robotics Initiative that serves as the nation’s long-term
vision and strategy across the entire Greek robotics ecosystem. Also, certain societal
drivers should be key in the areas of focus. Safety and security is an area of national
importance necessitating a national initiative, while agrifood, maritime and logistics
provide opportunities for internationally leading innovation.
We recommend the establishment of a mission-driven, government-funded, organization
advancing unmanned vehicles in societal drivers of national importance, and Greece should
leverage its unique geography and become a living testbed of robotics innovation turning the
country into a development site for exportable technologies. In our opinion, universities
should create Centers of Excellence in robotics and AI as well as consider
innovation-leading research institutes such as the Italian Institute of Technology. We
recommend investing in robotics education using Maker Spaces in order to prepare the
workforce with 21st century skills to become Industry 4.0 innovators. Furthermore, we
believe that the government should collect, measure, and analyze data on the robotics
industry, robotics uses, labor shifts, and brain gain and promote awareness via a Hellenic
Robotics Day. And finally, the government should regulate robot safety without stifling
innovation, provide safe experimentation areas and mechanisms for certifying safety of
locally developed robots. This monograph has many additional suggestions that enhance the
above main recommendations. As authors, we advocate bringing the robotics ecosystem together
in order to sharpen and expand these findings to an ambitious, long-term, and detailed
national strategy and roadmap for robotics in the AI era.},
issn = {1935-8253},
url = {http://dx.doi.org/10.1561/2300000069}
}
@article{wells2020-ltlf,
title = {LTLf Synthesis on Probabilistic Systems},
author = {Wells, Andrew M. and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},
journal = {Electronic Proceedings in Theoretical Computer Science},
month = sep,
year = {2020},
volume = {326},
pages = {166--181},
doi = {10.4204/eptcs.326.11},
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.},
issn = {2075-2180},
keyword = {planning from high-level specifications, uncertainty},
publisher = {Open Publishing Association},
url = {http://dx.doi.org/10.4204/EPTCS.326.11}
}
@article{litsa2020-metabolite-prediction,
title = {Prediction of drug metabolites using neural machine translation},
author = {Litsa, Eleni E. and Das, Payel and Kavraki, Lydia E.},
journal = {Chemical Science},
month = sep,
year = {2020},
pages = {12777--12788},
doi = {10.1039/D0SC02639E},
abstract = {Metabolic processes in the human body can alter the structure of a drug affecting
its efficacy and safety. As a result, the investigation of the metabolic fate of a candidate
drug is an essential part of drug design studies. Computational approaches have been
developed for the prediction of possible drug metabolites in an effort to assist the
traditional and resource-demanding experimental route. Current methodologies are based upon
metabolic transformation rules, which are tied to specific enzyme families and therefore
lack generalization, and additionally may involve manual work from experts limiting
scalability. We present a rule-free, end-to-end learning-based method for predicting
possible human metabolites of small molecules including drugs. The metabolite prediction
task is approached as a sequence translation problem with chemical compounds represented
using the SMILES notation. We perform transfer learning on a deep learning transformer model
for sequence translation, originally trained on chemical reaction data, to predict the
outcome of human metabolic reactions. We further build an ensemble model to account for
multiple and diverse metabolites. Extensive evaluation reveals that the proposed method
generalizes well to different enzyme families, as it can correctly predict metabolites
through phase I and phase II drug metabolism as well as other enzymes. Compared to existing
rule-based approaches, our method has equivalent performance on the major enzyme families
while it additionally finds metabolites through less common enzymes. Our results indicate
that the proposed approach can provide a comprehensive study of drug metabolism that does
not restrict to the major enzyme families and does not require the extraction of
transformation rules.},
issue = {11},
publisher = {The Royal Society of Chemistry},
url = {http://dx.doi.org/10.1039/D0SC02639E}
}
@article{devaurs2020-compstatin,
title = {Computational analysis of complement inhibitor compstatin using molecular dynamics},
author = {Devaurs, Didier and Antunes, Dinler A. and Kavraki, Lydia E.},
journal = {Journal of Molecular Modeling},
month = aug,
year = {2020},
volume = {26},
number = {231},
doi = {10.1007/s00894-020-04472-8},
abstract = {The complement system plays a major role in human immunity, but its abnormal
activation can have severe pathological impacts. By mimicking a natural mechanism of
complement regulation, the small peptide compstatin has proven to be a very promising
complement inhibitor. Over the years, several compstatin analogs have been created, with
improved inhibitory potency. A recent analog is being developed as a candidate drug against
several pathological conditions, including COVID-19. However, the reasons behind its higher
potency and increased binding affinity to complement proteins are not fully clear. This
computational study highlights the mechanistic properties of several compstatin analogs,
thus complementing previous experimental studies. We perform molecular dynamics simulations
involving six analogs alone in solution and two complexes with compstatin bound to
complement component 3. These simulations reveal that all the analogs we consider, except
the original compstatin, naturally adopt a pre-bound conformation in solution.
Interestingly, this set of analogs adopting a pre-bound conformation includes analogs that
were not known to benefit from this behavior. We also show that the most recent compstatin
analog (among those we consider) forms a stronger hydrogen bond network with its complement
receptor than an earlier analog.},
}
@article{antunes2020-hla-arena,
title = {{HLA}-{A}rena: a customizable environment for the structural modeling and analysis of
peptide-{HLA} complexes for cancer immunotherapy},
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.},
journal = {JCO Clinical Cancer Informatics},
month = jul,
year = {2020},
volume = {4},
pages = {623--636},
doi = {10.1200/CCI.19.00123},
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.},
keyword = {fundamentals of protein modeling, proteins and drugs, other biomedical computing},
note = {PMID: 32667823, PMCID: 7397777}
}
@article{abella2020-frontiers-random-forest,
title = {Large-scale structure-based prediction of stable peptide binding to Class I HLAs using
random forests},
author = {Abella, Jayvee R. and Antunes, Dinler A. and Clementi, Cecilia and Kavraki, Lydia E.},
journal = {Frontiers in Immunology},
month = jul,
year = {2020},
volume = {11},
number = {1583},
doi = {10.3389/fimmu.2020.01583},
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.},
keyword = {fundamentals of protein modeling, proteins and drugs, other biomedical computing},
note = {PMID: 32793224, PMCID: PMC7387700}
}
@article{luna2020a-scalable-motion-planner-for-high-dimensional,
title = {A Scalable Motion Planner for High-Dimensional Kinematic Systems},
author = {Luna, Ryan and Moll, Mark and Badger, Julia M. and Kavraki, Lydia E.},
journal = {International Journal of Robotics Research},
month = apr,
year = {2020},
volume = {39},
pages = {361--388},
doi = {10.1177/0278364919890408},
abstract = {Sampling-based algorithms are known for their ability to effectively compute paths
for high-dimensional robots in relatively short times. The same algorithms, however, are
also notorious for poor quality solution paths, particularly as the dimensionality of the
system grows. This work proposes a new probabilistically complete sampling-based algorithm,
XXL, specially designed to plan the motions of high-dimensional mobile manipulators and
related platforms. Using a novel sampling and connection strategy that guides a set of
points mapped on the robot through the workspace, XXL scales to realistic manipulator
platforms with dozens of joints by focusing the search of the robot's configuration space to
specific degrees-of-freedom that affect motion in particular portions of the workspace.
Simulated planning scenarios with the Robonaut2 platform and planar kinematic chains confirm
that XXL exhibits competitive solution times relative to many existing works while obtaining
execution-quality solution paths. Solutions from XXL are of comparable quality to costaware
methods even though XXL does not explicitly optimize over any particular criteria, and are
computed in an order of magnitude less time. Furthermore, observations about the performance
of sampling-based algorithms on high-dimensional manipulator planning problems are presented
that reveal a cautionary tale regarding two popular guiding heuristics used in these
algorithms, indicating that a nearly random search may outperform the state-of-the-art when
defining such heuristics is known to be difficult.},
issue = {4}
}
@article{hernandez2020increasing-robot-autonomy-via-motion,
title = {Increasing Robot Autonomy via Motion Planning and an Augmented Reality Interface},
author = {Hern{\'a}ndez, Juan David and Sobti, Shlok and Sciola, Anthony and Moll, Mark and Kavraki, Lydia E.},
journal = {IEEE Robotics and Automation Letters},
month = apr,
year = {2020},
volume = {5},
number = {2},
pages = {1017--1023},
doi = {10.1109/LRA.2020.2967280},
abstract = {Recently, there has been a growing interest in robotic systems that are able to
share workspaces and collaborate with humans. Such collaborative scenarios require efficient
mechanisms to communicate human requests to a robot, as well as to transmit robot
interpretations and intents to humans. Recent advances in augmented reality (AR)
technologies have provided an alternative for such communication. Nonetheless, most of the
existing work in human-robot interaction with AR devices is still limited to robot motion
programming or teleoperation. In this paper, we present an alternative approach to command
and collaborate with robots. Our approach uses an AR interface that allows a user to specify
high-level requests to a robot, to preview, approve or modify the computed robot motions.
The proposed approach exploits the robot's decisionmaking capabilities instead of requiring
low-level motion specifications provided by the user. The latter is achieved by using a
motion planner that can deal with high-level goals corresponding to regions in the robot
configuration space. We present a proof of concept to validate our approach in different
test scenarios, and we present a discussion of its applicability in collaborative
environments.},
}
@article{kim2020improving-the-organization-and-interactivity-of-metabolic,
title = {Improving the organization and interactivity of metabolic pathfinding with precomputed
pathways},
author = {Kim, Sarah M. and Pe{\~n}a, Matthew I. and Moll, Mark and Bennett, George N. and Kavraki, Lydia E.},
journal = {BMC Bioinformatics},
month = jan,
year = {2020},
volume = {21},
pages = {13},
doi = {10.1186/s12859-019-3328-x},
abstract = {Background: The rapid growth of available knowledge on metabolic processes across
thousands of species continues to expand the possibilities of producing chemicals by
combining pathways found in different species. Several computational search algorithms have
been developed for automating the identification of possible heterologous pathways; however,
these searches may return thousands of pathway results. Although the large number of results
are in part due to the large number of possible compounds and reactions, a subset of core
reaction modules is repeatedly observed in pathway results across multiple searches,
suggesting that some subpaths between common compounds were more consistently explored than
others.
To reduce the resources spent on searching the same metabolic space, a new meta-algorithm
for metabolic pathfinding, Hub Pathway search with Atom Tracking (HPAT), was developed to
take advantage of a precomputed network of subpath modules. To investigate the efficacy of
this method, we created a table describing a network of common hub metabolites and how they
are biochemically connected and only offloaded searches to and from this hub network onto an
interactive webserver capable of visualizing the resulting pathways.
Results: A test set of nineteen known pathways taken from literature and metabolic databases
were used to evaluate if HPAT was capable of identifying known pathways. HPAT found the
exact pathway for eleven of the nineteen test cases using a diverse set of precomputed
subpaths, whereas a comparable pathfinding search algorithm that does not use precomputed
subpaths found only seven of the nineteen test cases. The capability of HPAT to find novel
pathways was demonstrated by its ability to identify novel 3-hydroxypropanoate (3-HP)
synthesis pathways. As for pathway visualization, the new interactive pathway filters enable
a reduction of the number of displayed pathways from hundreds down to less than ten pathways
in several test cases, illustrating their utility in reducing the amount of presented
information while retaining pathways of interest.
Conclusions: This work presents the first step in incorporating a precomputed subpath
network into metabolic pathfinding and demonstrates how this leads to a concise, interactive
visualization of pathway results. The modular nature of metabolic pathways is exploited to
facilitate efficient discovery of alternate pathways.},
issue = {1},
keyword = {metabolic pathfinding; precomputation; atom mapping; graph search},
note = {PMID: 31924164, PMCID: PMC6954563}
}
@article{varava2020robotics-inspired-molecular-caging,
title = {A Robotics-Inspired Screening Algorithm for Molecular Caging Prediction},
author = {Kravchenko, Oleksandr and Varava, Anastasiia and Pokorny, Florian T. and Devaurs, Didier and Kavraki, Lydia E. and Kragic, Danica},
journal = {Journal of Chemical Information and Modeling},
year = {2020},
volume = {60},
number = {3},
pages = {1302--1316},
doi = {10.1021/acs.jcim.9b00945},
abstract = {We define a molecular caging complex as a pair of molecules in which one molecule
(the "host" or "cage") possesses a cavity that can encapsulate the other molecule (the
"guest") and prevent it from escaping. Molecular caging complexes can be useful in
applications such as molecular shape sorting, drug delivery, and molecular immobilization in
materials science, to name just a few. However, the design and computational discovery of
new caging complexes is a challenging task, as it is hard to predict whether one molecule
can encapsulate another because their shapes can be quite complex. In this paper, we propose
a computational screening method that predicts whether a given pair of molecules form a
caging complex. Our method is based on a caging verification algorithm that was designed by
our group for applications in robotic manipulation. We tested our algorithm on three pairs
of molecules that were previously described in a pioneering work on molecular caging
complexes and found that our results are fully consistent with the previously reported ones.
Furthermore, we performed a screening experiment on a data set consisting of 46 hosts and
four guests and used our algorithm to predict which pairs are likely to form caging
complexes. Our method is computationally efficient and can be integrated into a screening
pipeline to complement experimental techniques.},
note = {PMCID: PMC7307881},
url = {https://doi.org/10.1021/acs.jcim.9b00945}
}
@article{thais2020,
title = {Structural Modeling and Molecular Dynamics of the Immune Checkpoint Molecule HLA-G},
author = {Arns, Thais and Antunes, Dinler A. and Abella, Jayvee R. and Rigo, Maurício M. and Kavraki, Lydia E. and Giuliatti, Silvana and Donadi, Eduardo A.},
journal = {Frontiers in Immunology},
year = {2020},
volume = {11},
pages = {2882},
doi = {10.3389/fimmu.2020.575076},
abstract = {HLA-G is considered to be an immune checkpoint molecule, a function that is closely
linked to the structure and dynamics of the different HLA-G isoforms. Unfortunately, little
is known about the structure and dynamics of these isoforms. For instance, there are only
seven crystal structures of HLA-G molecules, being all related to a single isoform, and in
some cases lacking important residues associated to the interaction with leukocyte
receptors. In addition, they lack information on the dynamics of both membrane-bound HLA-G
forms, and soluble forms. We took advantage of in silico strategies to disclose the dynamic
behavior of selected HLA-G forms, including the membrane-bound HLA-G1 molecule, soluble
HLA-G1 dimer, and HLA-G5 isoform. Both the membrane-bound HLA-G1 molecule and the soluble
HLA-G1 dimer were quite stable. Residues involved in the interaction with ILT2 and ILT4
receptors (α3 domain) were very close to the lipid bilayer in the complete HLA-G1 molecule,
which might limit accessibility. On the other hand, these residues can be completely exposed
in the soluble HLA-G1 dimer, due to the free rotation of the disulfide bridge (Cys42/Cys42).
In fact, we speculate that this free rotation of each protomer (i.e., the chains composing
the dimer) could enable alternative binding modes for ILT2/ILT4 receptors, which in turn
could be associated with greater affinity of the soluble HLA-G1 dimer. Structural analysis
of the HLA-G5 isoform demonstrated higher stability for the complex containing the peptide
and coupled β2-microglobulin, while structures lacking such domains were significantly
unstable. This study reports for the first time structural conformations for the HLA-G5
isoform and the dynamic behavior of HLA-G1 molecules under simulated biological conditions.
All modeled structures were made available through GitHub (https://github.com/KavrakiLab/),
enabling their use as templates for modeling other alleles and isoforms, as well as for
other computational analyses to investigate key molecular interactions.},
issn = {1664-3224},
note = {PMCID: PMC7677236},
url = {https://www.frontiersin.org/article/10.3389/fimmu.2020.575076}
}
@article{pan2020augmenting-control-policies,
title = {Augmenting Control Policies with Motion Planning for Robust and Safe Multi-robot
Navigation},
author = {Pan, Tianyang and Verginis, Christos K. and Wells, Andrew M. and Kavraki, Lydia E. and Dimarogonas, Dimos V.},
booktitle = {2020 IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2020},
pages = {6975--6981},
doi = {10.1109/IROS45743.2020.9341153},
abstract = {This work proposes a novel method of incorporating calls to a motion planner inside
a potential field control policy for safe multi-robot navigation with uncertain dynamics.
The proposed framework can handle more general scenes than the control policy and has low
computational costs. Our work is robust to uncertain dynamics and quickly finds high-quality
paths in scenarios generated from real-world floor plans. In the proposed approach, we
attempt to follow the control policy as much as possible, and use calls to the motion
planner to escape local minima. Trajectories returned from the motion planner are followed
using a path-following controller guaranteeing robustness. We demonstrate the utility of our
approach with experiments based on floor plans gathered from real buildings.},
keyword = {multi-robot systems}
}
@article{konev2020-3d-printing,
title = {Machine Learning Guided {3D} Printing of Tissue Engineering Scaffolds},
author = {Conev, Anja and Litsa, Eleni and Perez, Marissa and Diba, Mani and Mikos, Antonios and Kavraki, Lydia E.},
journal = {Tissue Engineering Part A},
year = {2020},
volume = {26},
pages = {1359--1368},
doi = {10.1089/ten.TEA.2020.0191},
abstract = {Various material compositions have been successfully used in 3D printing with
promising applications as scaffolds in tissue engineering. However, identifying suitable
printing conditions for new materials requires extensive experimentation in a time and
resource-demanding process. This study investigates the use of Machine Learning (ML) for
distinguishing between printing configurations that are likely to result in low quality
prints and printing configurations that are more promising as a first step towards the
development of a recommendation system for identifying suitable printing conditions. The
ML-based framework takes as input the printing conditions regarding the material composition
and the printing parameters and predicts the quality of the resulting print as either "low"
or "high". We investigate two ML-based approaches: a direct classification-based approach
that trains a classifier to distinguish between "low" and "high" quality prints and an
indirect approach that uses a regression ML model that approximates the values of a printing
quality metric. Both models are built upon Random Forests. We trained and evaluated the
models on a dataset that was generated in a previous study which investigated fabrication of
porous polymer scaffolds by means of extrusion-based 3D printing with a full-factorial
design. Our results show that both models were able to correctly label the majority of the
tested configurations while a simpler linear ML model was not effective. Additionally our
analysis showed that a full factorial design for data collection can lead to redundancies in
the data, in the context of ML, and we propose a more efficient data collection strategy.},
issue = {23-24}
}
@article{abella2020-pnas,
title = {Markov state modeling reveals alternative unbinding pathways for
peptide{\textendash}{MHC} complexes},
author = {Abella, Jayvee R. and Antunes, Dinler and Jackson, Kyle and Liz{\'e}e, Gregory and Clementi, Cecilia and Kavraki, Lydia E.},
journal = {Proceedings of the National Academy of Sciences},
year = {2020},
volume = {117},
number = {48},
pages = {30610--30618},
doi = {10.1073/pnas.2007246117},
abstract = {Peptide binding to MHC receptors is part of a central biological process that
enables our immune system to attack diseased cells. We use molecular simulations to
illuminate the mechanisms driving stable peptide{\textendash}MHC binding. Our simulation
framework produces an atomistic model of the unbinding dynamics for a given
peptide{\textendash}MHC, which quantifies transitions between the major states of the system
(bound, intermediate, and unbound). We applied this framework to study the binding of a
SARS-CoV peptide to the HLA-A*24:02 receptor. This work revealed the unexpected importance
of peptide{\textquoteright}s position 4 in driving the stability of the complex, a finding
with broader biomedical implications. Our methods can be applied to other
peptide{\textendash}MHC complexes, requiring only a 3D model as input.Peptide binding to
major histocompatibility complexes (MHCs) is a central component of the immune system, and
understanding the mechanism behind stable peptide{\textendash}MHC binding will aid the
development of immunotherapies. While MHC binding is mostly influenced by the identity of
the so-called anchor positions of the peptide, secondary interactions from nonanchor
positions are known to play a role in complex stability. However, current MHC-binding
prediction methods lack an analysis of the major conformational states and might
underestimate the impact of secondary interactions. In this work, we present an atomically
detailed analysis of peptide{\textendash}MHC binding that can reveal the contributions of
any interaction toward stability. We propose a simulation framework that uses both umbrella
sampling and adaptive sampling to generate a Markov state model (MSM) for a
coronavirus-derived peptide (QFKDNVILL), bound to one of the most prevalent MHC receptors in
humans (HLA-A24:02). While our model reaffirms the importance of the anchor positions of the
peptide in establishing stable interactions, our model also reveals the underestimated
importance of position 4 (p4), a nonanchor position. We confirmed our results by simulating
the impact of specific peptide mutations and validated these predictions through competitive
binding assays. By comparing the MSM of the wild-type system with those of the D4A and D4P
mutations, our modeling reveals stark differences in unbinding pathways. The analysis
presented here can be applied to any peptide{\textendash}MHC complex of interest with a
structural model as input, representing an important step toward comprehensive modeling of
the MHC class I pathway.Code for umbrella sampling, adaptive sampling, and MSM analysis, as
well as representative structures, can be found in Github at
https://github.com/KavrakiLab/adaptive-samplingpmhc. Simulation data are available upon request.},
issn = {0027-8424},
publisher = {National Academy of Sciences},
url = {https://www.pnas.org/content/117/48/30610}
}
@article{devaurs2019using-parallelized-incremental-meta-docking,
title = {Using parallelized incremental meta-docking can solve the conformational sampling issue
when docking large ligands to proteins},
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},
month = sep,
year = {2019},
volume = {20},
number = {1},
pages = {42},
doi = {10.1186/s12860-019-0218-z},
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},
keyword = {proteins and drugs},
note = {PMID: 31488048, PMCID: PMC6729087}
}
@article{wells2019learning-feasibility-for-tmp,
title = {Learning Feasibility for Task and Motion Planning in Tabletop Environments},
author = {Wells, Andrew M. and Dantam, Neil T. and Shrivastava, Anshumali and Kavraki, Lydia E.},
journal = {IEEE Robotics and Automation Letters},
month = apr,
year = {2019},
volume = {4},
number = {2},
pages = {1255--1262},
doi = {10.1109/LRA.2019.2894861},
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},
keyword = {planning from high-level specifications},
note = {PMID: 31058229, PMCID: PMC6491048}
}
@article{wang2019point-based-policy,
title = {Point-Based Policy Synthesis for {POMDP}s with Boolean and Quantitative Objectives},
author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.},
journal = {IEEE Robotics and Automation Letters},
month = apr,
year = {2019},
volume = {4},
number = {2},
pages = {1860--1867},
doi = {10.1109/LRA.2019.2898045},
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.},
keyword = {planning from high-level specifications}
}
@article{he2019automated-abstraction-of-manipulation,
title = {Automated Abstraction of Manipulation Domains for Cost-Based Reactive Synthesis},
author = {He, K. and Lahijanian, M. and Kavraki, L. E. and Vardi, Moshe Y.},
journal = {IEEE Robotics and Automation Letters},
month = apr,
year = {2019},
volume = {4},
number = {2},
pages = {285--292},
doi = {10.1109/LRA.2018.2889191},
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.},
keyword = {planning from high-level specifications}
}
@article{litsa2019atom-mapping,
title = {Machine Learning Guided Atom Mapping of Metabolic Reactions},
author = {Litsa, Eleni E. and Pena, Matthew I. and Moll, Mark and Giannakopoulos, George and Bennett, George N. and Kavraki, Lydia E.},
journal = {Journal of Chemical Information and Modeling},
year = {2019},
volume = {59},
number = {3},
pages = {1121--1135},
doi = {10.1021/acs.jcim.8b00434},
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.},
keyword = {metabolic networks},
note = {PMID: 30500191}
}
@article{kingston2019exploring-implicit-spaces-for-constrained,
title = {Exploring Implicit Spaces for Constrained Sampling-Based Planning},
author = {Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.},
journal = {International Journal of Robotics Research},
year = {2019},
volume = {38},
number = {10-11},
pages = {1151--1178},
doi = {10.1177/0278364919868530},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{hernandez2019online-motion-planning-auvs,
title = {Online Motion Planning for Unexplored Underwater Environments using Autonomous
Underwater Vehicles},
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},
year = {2019},
volume = {36},
pages = {370--396},
doi = {10.1002/rob.21827},
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).},
issue = {2},
keyword = {other robotics}
}
@article{antunes2019structure-based-methods-for-binding,
title = {Structure-based methods for binding mode and binding affinity prediction for
peptide-{MHC} complexes},
author = {Antunes, Dinler A. and Abella, Jayvee R. and Devaurs, Didier and Rigo, Maur\'{i}cio M. and Kavraki, Lydia E.},
journal = {Current Topics in Medicinal Chemistry},
year = {2019},
volume = {19},
number = {1},
doi = {10.2174/1568026619666181224101744},
abstract = {Understanding the mechanisms involved in the activation of an immune response is
essential to many fields in human health, including vaccine development and personalized
cancer immunotherapy. A central step in the activation of the adaptive immune response is
the recognition, by T-cell lymphocytes, of peptides displayed by a special type of receptor
known as Major Histocompatibility Complex (MHC). Considering the key role of MHC receptors
in T-cell activation, the computational prediction of peptide binding to MHC has been an
important goal for many immunological applications. Sequence-based methods have become the
gold standard for peptide-MHC binding affinity prediction, but structure-based methods are
expected to provide more general predictions (i.e., predictions applicable to all types of
MHC receptors). In addition, structural modeling of peptide-MHC complexes has the potential
to uncover yet unknown drivers of T-cell activation, thus allowing for the development of
better and safer therapies. In this review, we discuss the use of computational methods for
the structural modeling of peptide-MHC complexes (i.e., binding mode prediction) and for the
structure-based prediction of binding affinity.},
keyword = {proteins and drugs, molecular docking, binding mode prediction, binding affinity
prediction, peptide-MHC complexes, immunogenicity, T-cell activation},
note = {PMID: 30582480, PMCID: PMC6361695}
}
@article{abella2019-apegen,
title = {APE-Gen: A Fast Method for Generating Ensembles of Bound Peptide-MHC Conformations},
author = {Abella, Jayvee R. and Antunes, Dinler A. and Clementi, Cecilia and Kavraki, Lydia E.},
journal = {Molecules},
year = {2019},
volume = {24},
number = {5},
pages = {881},
doi = {10.3390/molecules24050881},
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.},
issn = {1420-3049},
keyword = {fundamentals of protein modeling},
note = {PMID: 30832312, PMCID: PMC6429480},
url = {http://www.mdpi.com/1420-3049/24/5/881}
}
@article{hruska2018quantitative-comparison-of-adaptive-sampling,
title = {Quantitative comparison of adaptive sampling methods for protein dynamics},
author = {Hruska, Eugen and Abella, Jayvee R. and N{\"u}ske, Feliks and Kavraki, Lydia E. and Clementi, Cecilia},
journal = {The Journal of Chemical Physics},
month = dec,
year = {2018},
volume = {149},
number = {24},
pages = {244119},
doi = {10.1063/1.5053582},
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.},
keyword = {fundamentals of protein modeling},
note = {PMID: 30599712}
}
@article{lagriffoul2018tmp-benchmarks,
title = {Platform-Independent Benchmarks for Task and Motion Planning},
author = {Lagriffoul, Fabien and Dantam, Neil and Garrett, Caelan and Akbari, Aliakbar and Srivastava, Siddharth and Kavraki, Lydia E.},
journal = {IEEE Robotics and Automation Letters},
month = oct,
year = {2018},
volume = {3},
pages = {3765--3772},
doi = {10.1109/LRA.2018.2856701},
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.},
issue = {4},
keyword = {planning from high-level specifications; uncertainty}
}
@article{dantam2018task-motion-kit,
title = {The Task Motion Kit},
author = {Dantam, Neil T. and Chaudhuri, Swarat and Kavraki, Lydia E.},
journal = {Robotics and Automation Magazine},
month = sep,
year = {2018},
volume = {25},
number = {3},
pages = {61--70},
doi = {10.1109/MRA.2018.2815081},
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.},
keyword = {planning from high-level specifications},
publisher = {IEEE}
}
@article{kingston2018sampling-based-methods-for-motion-planning,
title = {Sampling-Based Methods for Motion Planning with Constraints},
author = {Kingston, Zachary K. and Moll, Mark and Kavraki, Lydia E.},
journal = {Annual Review of Control, Robotics, and Autonomous Systems},
month = may,
year = {2018},
volume = {1},
pages = {159--185},
doi = {10.1146/annurev-control-060117-105226},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{muhayyuddin2018randomized-physics-based-motion-planning,
title = {Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain
Environments},
author = {Muhayyuddin and Moll, Mark and Kavraki, Lydia E. and Rosell, Jan},
journal = {IEEE Robotics and Automation Letters},
month = apr,
year = {2018},
volume = {3},
number = {2},
pages = {712--719},
doi = {10.1109/LRA.2017.2783445},
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.},
keyword = {kinodynamic systems}
}
@article{devaurs_16_icibm,
title = {Native state of complement protein {C3d} analysed via hydrogen exchange and
conformational sampling},
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.},
journal = {International Journal of Computational Biology and Drug Design},
year = {2018},
volume = {11},
number = {1/2},
pages = {90--113},
doi = {10.1504/IJCBDD.2018.10011903},
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.},
keyword = {fundamentals of protein modeling},
note = {PMID: 30700993, PMCID: PMC6349257}
}
@article{devaurs2018revealing-unknown-protein0structures,
title = {Revealing Unknown Protein Structures Using Computational Conformational Sampling Guided
by Experimental Hydrogen-Exchange Data},
author = {Devaurs, Didier and Antunes, Dinler A. and Kavraki, Lydia E.},
journal = {International Journal of Molecular Sciences},
year = {2018},
volume = {19},
number = {11},
pages = {3406},
doi = {10.3390/ijms19113406},
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.},
keyword = {fundamentals of protein modeling},
note = {PMID: 30384411, PMCID: PMC6280153}
}
@article{dantam2018incremental-tmp,
title = {An Incremental Constraint-Based Framework for Task and Motion Planning},
author = {Dantam, Neil T. and Kingston, Zachary K. and Chaudhuri, Swarat and Kavraki, Lydia E.},
journal = {International Journal of Robotics Research, vol. 37, no. 10, pp. 1134-1151. (Invited
Article)},
year = {2018},
doi = {10.1177/0278364918761570},
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.},
keyword = {planning from high-level specifications}
}
@article{antunes2018_dinc-hla-proof,
title = {General prediction of peptide-{MHC} binding modes using incremental docking: A proof of
concept},
author = {Antunes, Dinler A and Devaurs, Didier and Moll, Mark and Liz\'{e}e, Gregory and Kavraki, Lydia E},
journal = {Scientific Reports},
year = {2018},
volume = {8},
pages = {4327},
doi = {10.1038/s41598-018-22173-4},
abstract = {The class I major histocompatibility complex (MHC) is capable of binding peptides
derived from intracellular proteins and displaying them at the cell surface. The recognition
of these peptide-MHC (pMHC) complexes by T-cells is the cornerstone of cellular immunity,
enabling the elimination of infected or tumoral cells. T-cell-based immunotherapies against
cancer, which leverage this mechanism, can greatly benefit from structural analyses of pMHC
complexes. Several attempts have been made to use molecular docking for such analyses, but
pMHC structure remains too challenging for even state-of-the-art docking tools. To overcome
these limitations, we describe the use of an incremental meta-docking approach for
structural prediction of pMHC complexes. Previous methods applied in this context used
specific constraints to reduce the complexity of this prediction problem, at the expense of
generality. Our strategy makes no assumption and can potentially be used to predict binding
modes for any pMHC complex. Our method has been tested in a re-docking experiment,
reproducing the binding modes of 25 pMHC complexes whose crystal structures are available.
This study is a proof of concept that incremental docking strategies can lead to general
geometry prediction of pMHC complexes, with potential applications for immunotherapy against
cancer or infectious diseases.},
keyword = {proteins and drugs, peptide-docking, pHLA structure, geometry prediction, DINC,
cancer immunotherapy},
note = {PMCID: PMC5847594, PMID: 29531253}
}
@article{abella2018maintaining-and-enhancing-diversity-of-sampled,
title = {Maintaining and Enhancing Diversity of Sampled Protein Conformations in
Robotics-Inspired Methods},
author = {Abella, Jayvee R. and Moll, Mark and Kavraki, Lydia E.},
journal = {Journal of Computational Biology},
year = {2018},
volume = {25},
number = {1},
pages = {3--20},
doi = {10.1089/cmb.2017.0164},
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.},
keyword = {fundamentals of protein modeling},
note = {PMID: 29035572, PMCID: PMC5756939}
}
@article{antunes2017_dinc2,
title = {{DINC} 2.0: a new protein-peptide docking webserver using an incremental approach},
author = {Antunes, Dinler A and Moll, Mark and Devaurs, Didier and Jackson, KR and Liz\'{e}e, Gregory and Kavraki, Lydia E},
journal = {Cancer Research},
month = nov,
year = {2017},
volume = {77},
number = {21},
pages = {55--57},
doi = {10.1158/0008-5472.CAN-17-0511},
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.},
keyword = {proteins and drugs, other biomedical computing},
note = {PMCID: PMC5679007, PMID: 29092940}
}
@article{kim2017_pathfinding_review,
title = {A Review of Parameters and Heuristics for Guiding Metabolic Pathfinding},
author = {Kim, Sarah M. and Pe\~{n}a, Matthew I. and Moll, Mark and Bennett, George N. and Kavraki, Lydia E.},
journal = {Journal of Cheminformatics},
month = sep,
year = {2017},
volume = {9},
number = {1},
pages = {51},
doi = {10.1186/s13321-017-0239-6},
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.},
keyword = {metabolic networks},
note = {PMCID: PMC5602787, PMID: 29086092}
}
@article{novinskaya2016_defining_proj,
title = {Defining low-dimensional projections to guide protein conformational sampling},
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},
doi = {10.1089/cmb.2016.0144},
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.},
keyword = {fundamentals of protein modeling},
note = {PMID: 27892695}
}
@article{devaurs-17-fmb,
title = {Coarse-grained conformational sampling of protein structure improves the fit to
experimental hydrogen-exchange data},
author = {Devaurs, Didier and Antunes, Dinler A. and Papanastasiou, Malvina and Moll, Mark and Ricklin, Daniel and Lambris, John D. and Kavraki, Lydia E.},
journal = {Frontiers in Molecular Biosciences},
year = {2017},
volume = {4},
number = {13},
doi = {10.3389/fmolb.2017.00013},
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.},
keyword = {fundamentals of protein modeling},
note = {PMCID: PMC5344923, PMID: 28344973}
}
@article{antunes2017_frontiers-immunol,
title = {Interpreting {T}-cell cross-reactivity through structure: implications for {TCR}-based
cancer immunotherapy},
author = {Antunes, Dinler A and Rigo, Maur\'{i}cio M and Freitas, Martiela V and FA, Mendes Marcus and Sinigaglia, Marialva and Liz\'{e}e, Gregory and Kavraki, Lydia E and Selin, Liisa K and Cornberg, Markus and Vieira, Gustavo F},
journal = {Front. Immunol.},
year = {2017},
volume = {8},
number = {1210},
doi = {10.3389/fimmu.2017.01210},
abstract = {Immunotherapy has become one of the most promising avenues for cancer treatment,
making use of the patient's own immune system to eliminate cancer cells. Clinical trials
with T-cell-based immunotherapies have shown dramatic tumor regressions, being effective in
multiple cancer types and for many different patients. Unfortunately, this progress was
tempered by reports of serious (even fatal) side effects. Such therapies rely on the use of
cytotoxic T-cell lymphocytes, an essential part of the adaptive immune system. Cytotoxic
T-cells are regularly involved in surveillance and are capable of both eliminating diseased
cells and generating protective immunological memory. The specificity of a given T-cell is
determined through the structural interaction between the T-cell receptor (TCR) and a
peptide-loaded major histocompatibility complex (MHC); i.e., an intracellular
peptide–ligand displayed at the cell surface by an MHC molecule. However, a given TCR can
recognize different peptide–MHC (pMHC) complexes, which can sometimes trigger an unwanted
response that is referred to as T-cell cross-reactivity. This has become a major safety
issue in TCR-based immunotherapies, following reports of melanoma-specific T-cells causing
cytotoxic damage to healthy tissues (e.g., heart and nervous system). T-cell
cross-reactivity has been extensively studied in the context of viral immunology and tissue
transplantation. Growing evidence suggests that it is largely driven by structural
similarities of seemingly unrelated pMHC complexes. Here, we review recent reports about the
existence of pMHC ``hot-spots" for cross-reactivity and propose the existence of a TCR
interaction profile (i.e., a refinement of a more general TCR footprint in which some amino
acid residues are more important than others in triggering T-cell cross-reactivity). We also
make use of available structural data and pMHC models to interpret previously reported
cross-reactivity patterns among virus-derived peptides. Our study provides further evidence
that structural analyses of pMHC complexes can be used to assess the intrinsic likelihood of
cross-reactivity among peptide-targets. Furthermore, we hypothesize that some apparent
inconsistencies in reported cross-reactivities, such as a preferential directionality, might
also be driven by particular structural features of the targeted pMHC complex. Finally, we
explain why TCR-based immunotherapy provides a special context in which meaningful T-cell
cross-reactivity predictions can be made.},
keyword = {T-cell cross-reactivity, peptide–MHC complex, cross-reactivity hot-spots,
TCR-interacting surface, hierarchical clustering, TCR/pMHC, cancer immunotherapy},
note = {PMCID: PMC5632759, PMID: 29046675}
}
@article{bohg2016big-data-on-robotics,
title = {Big Data in Robotics},
author = {Bohg, Jeannette and Ciocarlie, Matei and Civera, Javier and Kavraki, Lydia E.},
journal = {Big Data},
month = dec,
year = {2016},
volume = {4},
number = {4},
pages = {195--196},
doi = {10.1089/big.2016.29013.rob},
keyword = {other robotics},
note = {PMID: 27992266}
}
@article{dantam2016unix,
title = {Unix Philosophy and the Real World: Control Software for Humanoid Robots},
author = {Dantam, Neil T. and B{\o}ndergaard, Kim and Johansson, Mattias A. and Furuholm, Tobias and Kavraki, Lydia E.},
journal = {Frontiers in Robotics and Artificial Intelligence},
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.},
keyword = {other robotics}
}
@article{moll2016structure-guided-selection-of-specificity-determining,
title = {Structure-Guided Selection of Specificity Determining Positions in the Human Kinome},
author = {Moll, Mark and Finn, Paul W. and Kavraki, Lydia E.},
journal = {BMC Genomics},
year = {2016},
volume = {17 (Suppl.\ 4)},
pages = {431},
doi = {10.1186/s12864-016-2790-3},
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.},
keyword = {functional annotation},
note = {PMID: 27556159, PMCID: PMC5001202}
}
@article{lahijanian2016iterative,
title = {Iterative Temporal Planning in Uncertain Environments with Partial Satisfaction
Guarantees},
author = {Lahijanian, Morteza and Maly, Matthew R. and Fried, Dror and Kavraki, Lydia E. and Kress-Gazit, Hadas and Vardi, Moshe Y.},
journal = {IEEE Transactions on Robotics},
year = {2016},
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.},
keyword = {planning from high-level specifications}
}
@article{kavraki-moll2016rss2014,
title = {Editorial: Special Issue on the 2014 ``{R}obotics: {S}cience \& {S}ystems'' Conference},
author = {Kavraki, Lydia E. and Moll, Mark},
journal = {International Journal of Robotics Research},
year = {2016},
volume = {3--4},
number = {1--3},
doi = {10.1177/0278364915608299},
keyword = {other robotics}
}
@article{moll-sucan2015benchmarking-motion-planning,
title = {Benchmarking Motion Planning Algorithms: An Extensible Infrastructure for Analysis and
Visualization},
author = {Moll, Mark and {\c S}ucan, Ioan A. and Kavraki, Lydia E},
journal = {IEEE Robotics \& Automation Magazine (Special Issue on Replicable and Measurable
Robotics Research)},
year = {2015},
volume = {22},
number = {3},
pages = {96--102},
doi = {10.1109/MRA.2015.2448276},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{mandal2015targetingsh2,
title = {Targeting the {Src} homology 2 ({SH2}) domain of signal transducer and activator of
transcription 6 ({STAT6}) with cell-permeable, phosphatase-stable phosphopeptide mimics
potently inhibits {Tyr641} phosphorylation and transcriptional activity},
author = {Mandal, Pijus K and Morlacchi, Pietro and Knight, John Morgan and Link, Todd M and Lee, Gilbert R. and Nurieva, Roza and Singh, Divyendu and Dhanik, Ankur and Kavraki, Lydia E. and Corry, David B. and Ladbury, John E. and McMurray, John S.},
journal = {Journal of Medicinal Chemistry},
year = {2015},
doi = {10.1021/acs.jmedchem.5b01321},
abstract = {Signal transducer and activator of transcription 6 (STAT6) transmits signals from
cytokines IL-4 and IL-13 and is activated in allergic airway disease. We are developing
phosphopeptide mimetics targeting the SH2 domain of STAT6 to block recruitment to
phosphotyrosine residues on IL-4 or IL-13 receptors and subsequent Tyr641 phosphorylation to
inhibit the expression of genes contributing to asthma. Structure-affinity relationship
studies showed that phosphopeptides based on Tyr631 from IL-4Rα bind with weak affinity to
STAT6 whereas replacing the pY+3 residue with simple aryl and alkyl amides resulted in
affinities in the mid to low nM range. A set of phosphatase-stable, cell-permeable prodrug
analogs inhibited cytokine-stimulated STAT6 phosphorylation in both Beas-2B human airway
cells and primary mouse T-lymphocytes at concentrations as low as 100 nM. IL-13-stimulated
expression of CCL26 (eotaxin-3) was inhibited in a dose-dependent manner, demonstrating that
targeting the SH2 domain blocks both phosphorylation and transcriptional activity of
STAT6.},
keyword = {proteins and drugs},
note = {PMCID: PMC5109833, PMID: 26506089}
}
@article{kavraki-likhachev2015rss2014,
title = {Editorial: Special Issue on the 2014 ``{R}obotics: {S}cience \& {S}ystems'' Conference},
author = {Kavraki, Lydia E. and Likhachev, Maxim},
journal = {Autonomous Robots},
year = {2015},
volume = {39},
number = {3},
doi = {10.1007/s10514-015-9482-8},
keyword = {other robotics}
}
@article{grady-moll2015extending-applicability-of,
title = {Extending the Applicability of {POMDP} Solutions to Robotic Tasks},
author = {Grady, Devin K. and Moll, Mark and Kavraki, Lydia E.},
journal = {IEEE Transactions on Robotics},
year = {2015},
volume = {31},
number = {4},
pages = {948--961},
doi = {10.1109/TRO.2015.2441511},
abstract = {Partially-Observable Markov Decision Processes (POMDPs) are used in many robotic
task classes from soccer to household chores. Determining an approximately optimal action
policy for POMDPs is PSPACE-complete, and the exponential growth of computation time
prohibits solving large tasks. This paper describes two techniques to extend the range of
robotic tasks that can be solved using a POMDP. Our first technique reduces the motion
constraints of a robot, and then uses state-of-the-art robotic motion planning techniques to
respect the true motion constraints at runtime. We then propose a novel task decomposition
that can be applied to some indoor robotic tasks. This decomposition transforms a long time
horizon task into a set of shorter tasks. We empirically demonstrate the performance gain
provided by these two techniques through simulated execution in a variety of environments.
Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude
that the techniques proposed in this paper can provide significant enhancement to current
POMDP solution techniques, extending the POMDP instances that can be solved to include
large, continuous-state robotic tasks.},
keyword = {uncertainty}
}
@article{antunes-15-eodd,
title = {Understanding the challenges of protein flexibility in drug design},
author = {Antunes, Dinler A. and Devaurs, Didier and Kavraki, Lydia E.},
journal = {Expert Opinion on Drug Discovery},
year = {2015},
volume = {10},
number = {12},
pages = {1301--1313},
doi = {10.1517/17460441.2015.1094458},
abstract = {Protein-ligand interactions play key roles in various metabolic pathways, and the
proteins involved in these interactions represent major targets for drug discovery.
Molecular docking is widely used to predict the structure of protein-ligand complexes, and
protein flexibility stands out as one of the most important and challenging issues for
binding mode prediction. Various docking methods accounting for protein flexibility have
been proposed, tackling problems of ever-increasing dimensionality. This paper presents an
overview of conformational sampling methods treating target flexibility during molecular
docking. Special attention is given to approaches considering full protein flexibility.
Contrary to what is frequently done, this review does not rely on classical biomolecular
recognition models to classify existing docking methods. Instead, it applies algorithmic
considerations, focusing on the level of flexibility accounted for. This review also
discusses the diversity of docking applications, from virtual screening of small drug-like
compounds to geometry prediction of protein-peptide complexes. Considering the diversity of
docking methods presented here, deciding which one is the best at treating protein
flexibility depends on the system under study and the research application. In virtual
screening experiments, ensemble docking can be used to implicitly account for large-scale
conformational changes, and selective docking can additionally consider local binding-site
rearrangements. In other cases, on-the-fly exploration of the whole protein-ligand complex
might be needed for accurate geometry prediction of the binding mode. Among other things,
future methods are expected to provide alternative binding modes, which will better reflect
the dynamic nature of protein-ligand interactions.},
keyword = {proteins and drugs},
note = {PMID: 26414598}
}
@article{plaku-kavraki2013falsification-of-ltl,
title = {Falsification of {LTL} safety properties in hybrid systems},
author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.},
journal = {International Journal on Software Tools for Technology Transfer (STTT)},
year = {2013},
volume = {15},
number = {4},
pages = {305--320},
doi = {10.1007/s10009-012-0233-2},
issn = {1433-2779},
keyword = {planning from high-level specifications},
publisher = {Springer Berlin / Heidelberg}
}
@article{moll-bordeaux2013software-for-project-based,
title = {Software for Project-Based Learning of Robot Motion Planning},
author = {Moll, Mark and Bordeaux, Janice and Kavraki, Lydia E},
journal = {Computer Science Education, Special Issue on Robotics in CS Education},
year = {2013},
volume = {23},
number = {4},
pages = {332--348},
doi = {10.1080/08993408.2013.847167},
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.},
keyword = {other robotics}
}
@article{gipson-moll2013sims-hybrid-method,
title = {{SIMS}: A hybrid method for rapid conformational analysis},
author = {Gipson, B and Moll, Mark and Kavraki, Lydia E},
journal = {PLOS ONE},
year = {2013},
volume = {8},
number = {7},
pages = {68826},
doi = {10.1371/journal.pone.0068826},
abstract = {Proteins are at the root of many biological functions, often performing complex
tasks as the result of large changes in their structure. Describing the exact details of
these conformational changes, however, remains a central challenge for computational biology
due the enormous computational requirements of the problem. This has engendered the
development of a rich variety of useful methods designed to answer specific questions at
different levels of spatial, temporal, and energetic resolution. These methods fall largely
into two classes: physically accurate, but computationally demanding methods and fast,
approximate methods. We introduce here a new hybrid modeling tool, the Structured Intuitive
Move Selector (SIMS), designed to bridge the divide between these two classes, while
allowing the benefits of both to be seamlessly integrated into a single framework. This is
achieved by applying a modern motion planning algorithm, borrowed from the field of
robotics, in tandem with a well-established protein modeling library. SIMS can combine
precise energy calculations with approximate or specialized conformational sampling routines
to produce rapid, yet accurate, analysis of the large-scale conformational variability of
protein systems. Several key advancements are shown, including the abstract use of
generically defined moves (conformational sampling methods) and an expansive probabilistic
conformational exploration. We present three example problems that SIMS is applied to and
demonstrate a rapid solution for each. These include the automatic determination of "active"
residues for the hinge-based system Cyanovirin-N, exploring conformational changes involving
long-range coordinated motion between non-sequential residues in Ribose-Binding Protein, and
the rapid discovery of a transient conformational state of Maltose-Binding Protein,
previously only determined by Molecular Dynamics. For all cases we provide energetic
validations using well-established energy fields, demonstrating this framework as a fast and
accurate tool for the analysis of a wide range of protein flexibility problems.},
keyword = {proteins and drugs},
note = {PMCID: PMC3720858, PMID: 23935893}
}
@article{dhanik-mcmurray2013dinc-new-autodock-based,
title = {DINC: A new AutoDock-based protocol for docking large ligands},
author = {Dhanik, Ankur and McMurray, John and Kavraki, Lydia E},
journal = {BMC Structural Biology},
year = {2013},
volume = {13},
number = {Suppl 1},
pages = {11},
doi = {10.1186/1472-6807-13-S1-S11},
abstract = {BACKGROUND:Using the popular program AutoDock, computer-aided docking of small
ligands with 6 or fewer rotatable bonds, is reasonably fast and accurate. However, docking
large ligands using AutoDock{\textquoteright}s recommended standard docking protocol is less
accurate and computationally slow.RESULTS:In our earlier work, we presented a novel
AutoDock-based incremental protocol (DINC) that addresses the limitations of
AutoDock{\textquoteright}s standard protocol by enabling improved docking of large ligands.
Instead of docking a large ligand to a target protein in one single step as done in the
standard protocol, our protocol docks the large ligand in increments. In this paper, we
present three detailed examples of docking using DINC and compare the docking results with
those obtained using AutoDock{\textquoteright}s standard protocol. We summarize the docking
results from an extended docking study that was done on 73 protein-ligand complexes
comprised of large ligands. We demonstrate not only that DINC is up to 2 orders of magnitude
faster than AutoDock{\textquoteright}s standard protocol, but that it also achieves the
speed-up without sacrificing docking accuracy. We also show that positional restraints can
be applied to the large ligand using DINC: this is useful when computing a docked
conformation of the ligand. Finally, we introduce a webserver for docking large ligands
using DINC.CONCLUSIONS:Docking large ligands using DINC is significantly faster than
AutoDock{\textquoteright}s standard protocol without any loss of accuracy. Therefore, DINC
could be used as an alternative protocol for docking large ligands. DINC has been
implemented as a webserver and is available at http://dinc.kavrakilab.org. Applications such
as therapeutic drug design, rational vaccine design, and others involving large ligands
could benefit from DINC and its webserver implementation.},
issn = {1472-6807},
keyword = {proteins and drugs},
note = {PMCID: PMC3952135, PMID: 24564952}
}
@article{bryant-moll2013combinatorial-clustering-of,
title = {Combinatorial clustering of residue position subsets predicts inhibitor affinity across
the human kinome},
author = {Bryant, Drew H and Moll, Mark and Finn, Paul W. and Kavraki, Lydia E},
journal = {PLoS Computational Biology},
year = {2013},
volume = {9},
number = {6},
pages = {1003087},
doi = {10.1371/journal.pcbi.1003087},
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.},
keyword = {functional annotation, proteins and drugs},
note = {PMCID: PMC3675009, PMID: 23754939}
}
@article{sucan-moll2012open-motion-planning,
title = {The Open Motion Planning Library},
author = {{\c S}ucan, Ioan A. and Moll, Mark and Kavraki, Lydia E},
journal = {IEEE Robotics \& Automation Magazine},
month = dec,
year = {2012},
volume = {19},
pages = {72--82},
doi = {10.1109/MRA.2012.2205651},
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).},
keyword = {fundamentals of sampling-based motion planning, other robotics},
note = {http://ompl.kavrakilab.org}
}
@article{gipson-hsu2012computational-models-of,
title = {Computational Models of Proteins Kinematics and Dynamics: Beyond Simulation},
author = {Gipson, B and Hsu, David and Kavraki, Lydia E and Latombe, Jean-Claude},
journal = {Annual Reviews of Analytical Chemistry},
month = apr,
year = {2012},
volume = {5},
pages = {273--291},
doi = {10.1146/annurev-anchem-062011-143024},
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.},
keyword = {fundamentals of protein modeling, kinodynamic systems},
msid = {NIHMS712423},
note = {PMCID: PMC4866812, PMID: 22524225}
}
@article{shehu-kavraki2012modeling-structures-and,
title = {Modeling Structures and Motions of Loops in Protein Molecules},
author = {Shehu, A. and Kavraki, Lydia E},
journal = {Entropy},
month = feb,
year = {2012},
volume = {14},
pages = {252--290},
doi = {10.3390/e14020252},
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.},
keyword = {fundamentals of protein modeling}
}
@article{bekris-grady2012safe-distributed-motion,
title = {Safe Distributed Motion Coordination for Second-Order Systems With Different Planning
Cycles},
author = {Bekris, Kostas E. and Grady, Devin K and Moll, Mark and Kavraki, Lydia E},
journal = {International Journal of Robotics Research},
month = feb,
year = {2012},
volume = {31},
number = {2},
pages = {129--150},
doi = {10.1177/0278364911430420},
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.},
chapter = {129},
keyword = {kinodynamic systems}
}
@article{sucan-kavraki2012sampling-based-tree-planner,
title = {A Sampling-Based Tree Planner for Systems With Complex Dynamics},
author = {Sucan, Ioan Alexandru and Kavraki, Lydia E},
journal = {IEEE Transactions on Robotics},
year = {2012},
volume = {28},
number = {1},
pages = {116--131},
doi = {10.1109/TRO.2011.2160466},
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.},
issn = {1552-3098},
keyword = {fundamentals of sampling-based motion planning}
}
@article{dhanik-mcmurray2012binding-modes-of,
title = {Binding Modes of Peptidomimetics Designed to Inhibit STAT3},
author = {Dhanik, A. and McMurray, John S and Kavraki, Lydia E},
journal = {PLoS ONE},
year = {2012},
volume = {7(12)},
pages = {51603},
doi = {10.1371/journal.pone.0051603},
abstract = {STAT3 is a transcription factor that has been found to be constitutively activated
in a number of human cancers. Dimerization of STAT3 via its SH2 domain and the subsequent
translocation of the dimer to the nucleus leads to transcription of anti-apoptotic genes.
Prevention of the dimerization is thus an attractive strategy for inhibiting the activity of
STAT3. Phosphotyrosine-based peptidomimetic inhibitors, which mimic pTyr-Xaa-Yaa-Gln motif
and have strong to weak binding affinities, have been previously investigated. It is
well-known that structures of protein-inhibitor complexes are important for understanding
the binding interactions and designing stronger inhibitors. Experimental structures of
inhibitors bound to the SH2 domain of STAT3 are, however, unavailable. In this paper we
describe a computational study that combined molecular docking and molecular dynamics to
model structures of 12 peptidomimetic inhibitors bound to the SH2 domain of STAT3. A
detailed analysis of the modeled structures was performed to evaluate the characteristics of
the binding interactions. We also estimated the binding affinities of the inhibitors by
combining MMPB/GBSA-based energies and entropic cost of binding. The estimated affinities
correlate strongly with the experimentally obtained affinities. Modeling results show
binding modes that are consistent with limited previous modeling studies on binding
interactions involving the SH2 domain and phosphotyrosine(pTyr)-based inhibitors. We also
discovered a stable novel binding mode that involves deformation of two loops of the SH2
domain that subsequently bury the C-terminal end of one of the stronger inhibitors. The
novel binding mode could prove useful for developing more potent inhibitors aimed at
preventing dimerization of cancer target protein STAT3.},
keyword = {proteins and drugs},
note = {PMCID: PMC3520966, PMID: 23251591}
}
@article{dhanik-kavraki2012protein-ligand-interactions-computational,
title = {Protein-ligand interactions: computational docking},
author = {Dhanik, A. and Kavraki, Lydia E},
journal = {Encyclopedia of Life Sciences},
year = {2012},
doi = {10.1002/9780470015902.a0004105.pub2},
abstract = {A pharmaceutical drug compound is usually a small organic molecule, also termed as
ligand, that binds to the target protein and alters the natural activity of the protein,
thus, leading to a therapeutic effect. Computational docking or computer-aided docking is an
extremely useful tool to gain an understanding of protein-ligand interactions which is
important for the drug discovery. Computational docking is the process of computationally
predicting the placement and binding affinity of the ligand in the binding pocket of the
protein. Docking methods rely on a search algorithm which computes the placement of the
ligand in the binding pocket and a scoring function which estimates the binding affinity,
i.e., how strongly the ligand interacts with the protein. A variety of methods have been
developed to solve the computational docking problems that range from simple point-matching
algorithms to explicit physical simulation methods.},
keyword = {proteins and drugs},
publisher = {John Wiley \& Sons Ltd}
}
@article{heath-bennett2011algorithm-for-efficient,
title = {An Algorithm for Efficient Identification of Branched Metabolic Pathways},
author = {Heath, A. P. and Bennett, G. N. and Kavraki, Lydia E},
journal = {Journal of Computational Biology},
month = nov,
year = {2011},
volume = {18},
number = {11},
pages = {1575--1597},
doi = {10.1089/cmb.2011.0165},
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.},
keyword = {metabolic networks},
note = {PMID: 21999288}
}
@article{bhatia-maly2011motion-planning-with,
title = {Motion Planning with Complex Goals},
author = {Bhatia, Amit and Maly, MR and Kavraki, Lydia E and Vardi, Moshe Y.},
journal = {Robotics Automation Magazine, IEEE},
month = sep,
year = {2011},
volume = {18},
number = {3},
pages = {55--64},
doi = {10.1109/MRA.2011.942115},
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].},
issn = {1070-9932},
keyword = {planning from high-level specifications}
}
@article{moll-bryant2011labelhash-server-and,
title = {The LabelHash Server and Tools for Substructure-Based Functional Annotation},
author = {Moll, Mark and Bryant, Drew H and Kavraki, Lydia E},
journal = {Bioinformatics},
month = aug,
year = {2011},
volume = {27},
number = {15},
pages = {2161--2162},
doi = {10.1093/bioinformatics/btr343},
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.},
keyword = {functional annotation},
note = {PMID: 21659320}
}
@article{heath-bennett2011identifying-branched-metabolic,
title = {Identifying Branched Metabolic Pathways by Merging Linear Metabolic Pathways},
author = {Heath, A. P. and Bennett, G. N. and Kavraki, Lydia E},
journal = {15th Annual International Conference on Research in Computational Molecular Biology
(RECOMB)},
year = {2011},
volume = {6577/2011},
pages = {70--84},
doi = {10.1007/978-3-642-20036-6_9},
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.},
keyword = {metabolic networks}
}
@article{moll-bryant2010labelhash-algorithm-for,
title = {The LabelHash Algorithm for Substructure Matching},
author = {Moll, Mark and Bryant, Drew H and Kavraki, Lydia E},
journal = {BMC Bioinformatics},
month = dec,
year = {2010},
volume = {11},
pages = {555},
doi = {10.1186/1471-2105-11-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.},
issn = {1471-2105},
keyword = {functional annotation},
note = {PMCID: PMC2996407, PMID: 21070651}
}
@article{stamati-clementi2010application-of-nonlinear,
title = {Application of nonlinear dimensionality reduction to characterize the conformational
landscape of small peptides},
author = {Stamati, H. and Clementi, C. and Kavraki, Lydia E},
journal = {Proteins},
month = jul,
year = {2010},
volume = {78},
number = {2},
pages = {223--235},
doi = {10.1002/prot.22526},
abstract = {The automatic classification of the wealth of molecular configurations gathered in
simulation in the form of a few coordinates that help to explain the main states and
transitions of the system is a recurring problem in computational molecular biophysics. We
use the recently proposed ScIMAP algorithm to automatically extract motion parameters from
simulation data. The procedure uses only molecular shape similarity and topology information
inferred directly from the simulated conformations, and is not biased by a priori known
information. The automatically recovered coordinates prove as excellent reaction coordinates
for the molecules studied and can be used to identify stable states and transitions, and as
a basis to build free-energy surfaces. The coordinates provide a better description of the
free energy landscape when compared with coordinates computed using principal components
analysis, the most popular linear dimensionality reduction technique. The method is first
validated on the analysis of the dynamics of an all-atom model of alanine dipeptide, where
it successfully recover all previously known metastable states. When applied to characterize
the simulated folding of a coarse-grained model of beta-hairpin, in addition to the folded
and unfolded states, two symmetric misfolding crossings of the hairpin strands are observed,
together with the most likely transitions from one to the other. Proteins 2010. (c) 2009
Wiley-Liss, Inc.},
keyword = {proteins and drugs},
msid = {NIHMS131834},
note = {PMCID: PMC2795065, PMID: 19731366}
}
@article{plaku-kavraki2010motion-planning-with,
title = {Motion Planning with Dynamics by a Synergistic Combination of Layers of Planning},
author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.},
journal = {IEEE Transactions on Robotics},
month = jun,
year = {2010},
volume = {26},
number = {3},
pages = {469--482},
doi = {10.1109/TRO.2010.2047820},
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.},
chapter = {469},
keyword = {kinodynamic systems, planning from high-level specifications}
}
@article{moll-bordeaux2010teaching-robot-motion,
title = {Teaching Robot Motion Planning},
author = {Moll, Mark and Bordeaux, Janice and Kavraki, Lydia E},
journal = {Computers in Education (Special Issue on Novel Approaches to Robotics Education)},
year = {2010},
volume = {20},
number = {3},
pages = {50--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.},
keyword = {other robotics},
url = {https://www.asee.org/papers-and-publications/publications/division-publications/computers-in-education-journal/volume-xx}
}
@article{heath-bennett2010finding-metabolic-pathways,
title = {Finding Metabolic Pathways Using Atom Tracking},
author = {Heath, A. P. and Bennett, G. N. and Kavraki, Lydia E},
journal = {Bioinformatics},
year = {2010},
volume = {26},
number = {12},
pages = {1548--1555},
doi = {10.1093/bioinformatics/btq223},
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},
keyword = {metabolic networks},
note = {PMID: 20421197, PMCID: PMC2881407}
}
@article{haspel-moll2010tracing-conformational-changes,
title = {Tracing conformational changes in proteins},
author = {Haspel, N. and Moll, Mark and Baker, M. L. and Chiu, W. and Kavraki, Lydia E},
journal = {BMC Structural Biology},
year = {2010},
volume = {10},
number = {Suppl. 1},
pages = {1},
doi = {10.1186/1472-6807-10-S1-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.},
keyword = {fundamentals of protein modeling, proteins and drugs},
note = {PMCID: PMC2873824, PMID: 20487508}
}
@article{bryant-moll2010analysis-of-substructural,
title = {Analysis of substructural variation in families of enzymatic proteins with applications
to protein function prediction},
author = {Bryant, Drew H and Moll, Mark and Chen, B. Y. and Fofanov, Viacheslav Y. and Kavraki, Lydia E},
journal = {BMC Bioinformatics},
year = {2010},
volume = {11},
number = {242},
pages = {242},
doi = {10.1186/1471-2105-11-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.},
keyword = {functional annotation, proteins and drugs},
note = {PMCID: PMC2885373, PMID: 20459833}
}
@article{shehu-kavraki2009multiscale-characterization-of,
title = {Multiscale characterization of protein conformational ensembles},
author = {Shehu, A. and Kavraki, Lydia E and Clementi, C.},
journal = {Proteins},
year = {2009},
volume = {76},
number = {4},
pages = {837--851},
doi = {10.1002/prot.22390},
abstract = {We propose a multiscale exploration method to characterize the conformational space
populated by a protein at equilibrium. The method efficiently obtains a large set of
equilibrium conformations in two stages: first exploring the entire space at a
coarse-grained level of detail, then narrowing a refined exploration to selected low-energy
regions. The coarse-grained exploration periodically adds all-atom detail to selected
conformations to ensure that the search leads to regions which maintain low energies in
all-atom detail. The second stage reconstructs selected low-energy coarse-grained
conformations in all-atom detail. A low-dimensional energy landscape associated with
all-atom conformations allows focusing the exploration to energy minima and their
conformational ensembles. The lowest energy ensembles are enriched with additional all-atom
conformations through further multiscale exploration. The lowest energy ensembles obtained
from the application of the method to three different proteins correctly capture the known
functional states of the considered systems.},
keyword = {proteins and drugs},
msid = {NIHMS130378},
note = {PMCID: PMC3164158, PMID: 19280604}
}
@article{plaku-kavraki2009hybrid-systems-from,
title = {Hybrid systems: from verification to falsification by combining motion planning and
discrete search},
author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.},
journal = {Formal Methods in System Design},
year = {2009},
volume = {34},
pages = {157--182},
doi = {10.1007/s10703-008-0058-5},
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.},
keyword = {planning from high-level specifications}
}
@article{heath-kavraki2009computational-challenges-in,
title = {Computational Challenges in Systems Biology},
author = {Heath, A. P. and Kavraki, Lydia E},
journal = {Computer Science Review},
year = {2009},
volume = {3},
number = {1},
pages = {1--17},
doi = {10.1016/j.cosrev.2009.01.002},
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.},
keyword = {other biomedical computing}
}
@article{haspel-geisbrecht2009multi-scale-characterization-of,
title = {Multi-scale Characterization of the Energy Landscape of Proteins with Application to
the {C3d/Efb-C} Complex},
author = {Haspel, N. and Geisbrecht, B. and Lambris, J.D. and Kavraki, Lydia E},
journal = {Proteins: Structure, function and bioinformatics},
year = {2009},
volume = {78},
number = {4},
pages = {1004--1014},
doi = {10.1002/prot.22624},
keyword = {proteins and drugs},
msid = {NIHMS153525},
note = {PMCID: PMC2827694, PMID: 19899169}
}
@article{bekris-tsianos2009safe-and-distributed,
title = {Safe and Distributed Kinodynamic Replanning for Vehicular networks},
author = {Bekris, Kostas E. and Tsianos, Konstantinos I. and Kavraki, Lydia E},
journal = {ACM/Springer Mobile Networks and Applications (MONET)},
year = {2009},
volume = {14},
number = {3},
pages = {292--308},
doi = {10.1007/s11036-009-0152-y},
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.},
keyword = {kinodynamic systems}
}
@article{haspel-ricklin2008electrostatic-contributions-drive,
title = {Electrostatic Contributions Drive the Interaction Between Staphylococcus aureus Protein
{Efb-C} and its Complement Target {C3d}},
author = {Haspel, N. and Ricklin, D. and Geisbrecht, B. and Lambris, J.D. and Kavraki, Lydia E},
journal = {Protein Science},
month = nov,
year = {2008},
volume = {17(11)},
pages = {1894--1906},
doi = {10.1110/ps.036624.108},
abstract = {The C3-inhibitory domain of Staphylococcus aureus extracellular fibrinogen-binding
protein (Efb-C) defines a novel three-helix bundle motif that regulates complement
activation. Previous crystallographic studies of Efb-C bound to its cognate sub-domain of
human C3 (C3d) identified Arg-131 and Asn-138 of Efb-C as key residues for its activity. In
order to characterize more completely the physical and chemical driving forces behind this
important interaction, we employed in this study a combination of structural, biophysical,
and computational methods to analyze the interaction of C3d with Efb-C and the single point
mutants R131A and N138A. Our results show that while these mutations do not drastically
affect the structure of the Efb-C/C3d recognition complex, they have significant adverse
effects on both the thermodynamic kinetic profiles of the resulting complexes. We also
characterized other key interactions along the Efb-C/C3d binding interface and found an
intricate network of salt bridges and hydrogen bonds that anchor Efb-C to C3d, resulting in
its potent complement inhibitory properties.},
keyword = {proteins and drugs},
note = {PMID: 18687868, PMCID: PMC2578803}
}
@article{shehu-kavraki2008unfolding-fold-of,
title = {Unfolding the Fold of Cyclic Cysteine-rich Peptides},
author = {Shehu, A. and Kavraki, Lydia E and Clementi, C.},
journal = {Protein Science},
year = {2008},
volume = {17},
pages = {482--493},
doi = {10.1110/ps.073142708},
abstract = {We propose a method to extensively characterize the native state ensemble of cyclic
cysteine-rich peptides. The method uses minimal information, namely, amino acid sequence and
cyclization, as a topological feature that characterizes the native state. The method does
not assume a specific disulfide bond pairing for cysteines and allows the possibility of
unpaired cysteines. A detailed view of the conformational space relevant for the native
state is obtained through a hierarchic multi-resolution exploration. A crucial feature of
the exploration is a geometric approach that efficiently generates a large number of
distinct cyclic conformations independently of one another. A spatial and energetic analysis
of the generated conformations associates a free-energy landscape to the explored
conformational space. Application to three long cyclic peptides of different folds shows
that the conformational ensembles and cysteine arrangements associated with free energy
minima are fully consistent with available experimental data. The results provide a detailed
analysis of the native state features of cyclic peptides that can be further tested in
experiment.},
keyword = {proteins and drugs},
note = {PMCID: PMC2248317, PMID: 18287281}
}
@article{kristensen-ward2008prediction-of-enzyme,
title = {Prediction of enzyme function based on {3D} templates of evolutionarily important amino
acids},
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},
journal = {BMC Bioinformatics},
year = {2008},
volume = {9},
doi = {10.1186/1471-2105-9-17},
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.},
keyword = {functional annotation},
note = {PMCID: PMC2219985, PMID: 18190718}
}
@article{heath-balazsi2008bipolarity-of-saccharomyces,
title = {Bipolarity of the saccharomyces cerevisiae genome},
author = {Heath, A. P. and Bal{\'a}zsi, G. and Kavraki, Lydia E},
journal = {International Conference on Bioinformatics and Biomedical Engineering (iCBBE)},
year = {2008},
pages = {330--333},
doi = {10.1109/ICBBE.2008.84},
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.},
keyword = {other biomedical computing}
}
@article{tsianos-sucan2007sampling-based-robot-motion,
title = {Sampling-based robot motion planning: Towards realistic applications},
author = {Tsianos, Konstantinos I. and Sucan, Ioan Alexandru and Kavraki, Lydia E},
journal = {Computer Science Review},
month = aug,
year = {2007},
volume = {1},
pages = {2--11},
doi = {10.1016/j.cosrev.2007.08.002},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{heath-kavraki2007from-coarse-grain-to,
title = {From coarse-grain to all-atom: Toward multiscale analysis of protein landscapes},
author = {Heath, A. P. and Kavraki, Lydia E and Clementi, C.},
journal = {Proteins: Structure, Function and Bioinformatics},
month = aug,
year = {2007},
volume = {68},
number = {3},
pages = {646--661},
doi = {10.1002/prot.21371},
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.},
keyword = {fundamentals of protein modeling},
note = {PMID: 17523187}
}
@article{shehu-kavraki2007on-characterization-of,
title = {On the Characterization of Protein Native State Ensembles},
author = {Shehu, A. and Kavraki, Lydia E and Clementi, C.},
journal = {Biophysical Journal},
year = {2007},
volume = {92},
number = {5},
pages = {1503--1511},
doi = {10.1529/biophysj.106.094409},
abstract = {Describing and understanding the biological function of a protein requires a
detailed structural and thermodynamic description of the protein{\textquoteright}s native
state ensemble. Obtaining such a description often involves characterizing equilibrium
fluctuations that occur beyond the nanosecond timescale. Capturing such fluctuations remains
nontrivial even for very long molecular dynamics and Monte Carlo simulations. We propose a
novel multiscale computational method to exhaustively characterize, in atomistic detail, the
protein conformations constituting the native state with no inherent timescale limitations.
Applications of this method to proteins of various folds and sizes show that thermodynamic
observables measured as averages over the native state ensembles obtained by the method
agree remarkably well with nuclear magnetic resonance data that span multiple timescales. By
characterizing equilibrium fluctuations at atomistic detail over a broad range of
timescales, from picoseconds to milliseconds, our method offers to complement current
simulation techniques and wet-lab experiments and can impact our understanding and
description of the relationship between protein flexibility and function.},
keyword = {proteins and drugs},
note = {PMCID: PMC1796840, PMID: 17158570}
}
@article{shehu-clementi2007sampling-conformation-space,
title = {Sampling Conformation Space to Model Equilibrium Fluctuations in Proteins},
author = {Shehu, A. and Clementi, C. and Kavraki, Lydia E},
journal = {Algorithmica},
year = {2007},
volume = {48},
pages = {303--327},
doi = {10.1007/s00453-007-0178-0},
abstract = {This paper proposes the Protein Ensemble Method (PEM) to model equilibrium
fluctuations in proteins where fragments of the protein polypeptide chain can move
independently of one another. PEM models global equilibrium fluctuations of a polypeptide
chain by combining local fluctuations of consecutive overlapping fragments of the chain.
Local fluctuations are computed by a probabilistic exploration that exploits analogies
between proteins and robots. All generated conformations are subjected to energy
minimization and then are weighted according to a Boltzmann distribution. Using the theory
of statistical mechanics the Boltzmann-weighted fluctuations corresponding to each fragment
are combined to obtain fluctuations for the entire protein. The agreement obtained between
PEM-modeled fluctuations, wet-lab experiment and guided simulation measurements, indicates
that PEM is able to reproduce with high accuracy protein equilibrium fluctuations that occur
over a broad range of timescales.},
keyword = {proteins and drugs}
}
@article{plaku-stamati2007fast-and-reliable,
title = {Fast and Reliable Analysis of Molecular Motion Using Proximity Relations and
Dimensionality Reduction},
author = {Plaku, E. and Stamati, H. and Clementi, C. and Kavraki, Lydia E},
journal = {Proteins: Structure, Function, and Bioinformatics},
year = {2007},
volume = {67},
number = {4},
pages = {897--907},
doi = {10.1002/prot.21337},
abstract = {The analysis of molecular motion starting from extensive sampling of molecular
configurations remains an important and challenging task in computational biology. Existing
methods require a significant amount of time to extract the most relevant motion information
from such data sets. In this work, we provide a practical tool for molecular motion
analysis. The proposed method builds upon the recent ScIMAP (Scalable Isomap) method, which,
by using proximity relations and dimensionality reduction, has been shown to reliably
extract from simulation data a few parameters that capture the main, linear and/or
nonlinear, modes of motion of a molecular system. The results we present in the context of
protein folding reveal that the proposed method characterizes the folding process
essentially as well as ScIMAP. At the same time, by projecting the simulation data and
computing proximity relations in a low-dimensional Euclidean space, it renders such analysis
computationally practical. In many instances, the proposed method reduces the computational
cost from several CPU months to just a few CPU hours, making it possible to analyze
extensive simulation data in a matter of a few hours using only a single processor. These
results establish the proposed method as a reliable and practical tool for analyzing motions
of considerably large molecular systems and proteins with complex folding mechanisms.},
keyword = {proteins and drugs},
note = {PMID: 17380507}
}
@article{plaku-kavraki2007distributed-computation-of,
title = {Distributed Computation of the KNN Graph for Large High-Dimensional Point Sets},
author = {Plaku, E. and Kavraki, Lydia E},
journal = {Journal of Parallel and Distributed Computing},
year = {2007},
volume = {67},
number = {3},
pages = {346--359},
doi = {10.1016/j.jpdc.2006.10.004},
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.},
keyword = {other robotics},
msid = {NIHMS18161},
note = {PMCID: PMC2764297, PMID: 19847318}
}
@article{chen-fofanov2007mash-pipeline-for,
title = {The {MASH} Pipeline for Protein Function Prediction and an Algorithm for the Geometric
Refinement of {3D} Motifs},
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},
journal = {Journal of Computational Biology},
year = {2007},
volume = {14},
number = {6},
pages = {791--816},
doi = {10.1089/cmb.2007.R017},
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.},
keyword = {functional annotation},
note = {PMID: 17691895}
}
@article{chen-bryant2007cavity-scaling-automated,
title = {Cavity Scaling: Automated Refinement of Cavity-Aware Motifs in Protein Function
Prediction},
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},
journal = {Journal of Bioinformatics and Computational Biology},
year = {2007},
volume = {5},
number = {2a},
pages = {353--382},
doi = {10.1142/S021972000700276X},
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.},
keyword = {functional annotation},
note = {PMID: 17589966}
}
@article{moll-kavraki2006path-planning-for,
title = {Path Planning for Deformable Linear Objects},
author = {Moll, Mark and Kavraki, Lydia E},
journal = {IEEE Transactions on Robotics},
month = aug,
year = {2006},
volume = {22},
number = {4},
pages = {625--636},
doi = {10.1109/TRO.2006.878933},
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.},
keyword = {fundamentals of sampling-based motion planning, other robotics}
}
@article{das-moll2006low-dimensional-free-energy-landscapes,
title = {Low-dimensional Free-energy Landscapes of Protein-Folding Reactions by Nonlinear
Dimensionality Reduction},
author = {Das, P. and Moll, Mark and Stamati, H. and Kavraki, Lydia E and Clementi, C.},
journal = {Proceedings of the National Academy of Sciences},
month = jun,
year = {2006},
volume = {103},
number = {26},
pages = {9885--9890},
doi = {10.1073/pnas.0603553103},
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.},
keyword = {fundamentals of protein modeling, proteins and drugs},
note = {PMCID: PMC1502548, PMID: 16785435}
}
@article{shehu-clementi2006modeling-protein-conformational,
title = {Modeling Protein Conformational Ensembles: From Missing Loops to Equilibrium
Fluctuations},
author = {Shehu, A. and Clementi, C. and Kavraki, Lydia E},
journal = {Proteins: Structure, Function and Bioinformatics},
year = {2006},
volume = {65},
number = {1},
pages = {164--179},
doi = {10.1002/prot.21060},
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.},
keyword = {functional annotation},
note = {PMID: 16917941}
}
@article{kristensen-chen2006recurrent-use-of,
title = {Recurrent Use of Evolutionary Importance for Functional Annotation of Proteins Based on
Local Structural Similarity},
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},
journal = {Protein Science},
year = {2006},
volume = {15},
number = {6},
pages = {1530--1536},
doi = {10.1110/ps.062152706},
keyword = {functional annotation},
note = {PMCID: PMC2242527, PMID: 16672239}
}
@article{ladd-bekris2005robotics-based-location-sensing,
title = {Robotics-Based Location Sensing using Wireless Ethernet (Invited)},
author = {Ladd, A. M. and Bekris, Kostas E. and Rudys, A. and Marceau, G. and Kavraki, Lydia E and Wallach, D. S.},
journal = {Wireless Networks (The Journal of Mobile Communication, Computation and
Information)},
month = jan,
year = {2005},
volume = {11},
number = {1-2},
pages = {189--204},
doi = {10.1007/s11276-004-4755-8},
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.},
keyword = {localization}
}
@article{zhang-white2005improving-conformational-searches,
title = {Improving Conformational Searches by Geometric Screening},
author = {Zhang, M. and White, R. A. and Wang, L. and Goldman, R. and Kavraki, Lydia E and Hassett, B.},
journal = {Bioinformatics},
year = {2005},
volume = {21},
number = {5},
pages = {624--630},
doi = {10.1093/bioinformatics/bti055},
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.},
keyword = {functional annotation},
note = {PMID: 15479715}
}
@article{plaku-bekris2005sampling-based-roadmap-of,
title = {Sampling-Based Roadmap of Trees for Parallel Motion Planning},
author = {Plaku, E. and Bekris, Kostas E. and Chen, B. Y. and Ladd, A. M. and Kavraki, Lydia E},
journal = {IEEE Transactions on Robotics},
year = {2005},
volume = {21},
number = {4},
pages = {597--608},
doi = {10.1109/TRO.2005.847599},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{argyros-bekris2005robot-homing-by,
title = {Robot Homing by Exploiting Panoramic Vision},
author = {Argyros, A. A. and Bekris, Kostas E. and Orphanoudakis, S. C. and Kavraki, Lydia E},
journal = {Autonomous Robots},
year = {2005},
volume = {19},
number = {1},
pages = {7--25},
doi = {10.1007/s10514-005-0603-7},
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},
keyword = {other robotics}
}
@article{ladd-bekris2004on-feasibility-of,
title = {On the Feasibility of Using Wireless Ethernet for Indoor Localization},
author = {Ladd, A. M. and Bekris, Kostas E. and Rudys, A. and Kavraki, Lydia E and Wallach, D. S.},
journal = {IEEE Transactions on Robotics and Automation},
month = jun,
year = {2004},
volume = {20},
number = {3},
pages = {555--559},
doi = {10.1109/TRA.2004.824948},
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.},
keyword = {localization}
}
@article{ladd-kavraki2004measure-theoretic-analysis,
title = {Measure Theoretic Analysis of Probabilistic Path Planning},
author = {Ladd, A. M. and Kavraki, Lydia E},
journal = {IEEE Transactions on Robotics and Automation},
month = apr,
year = {2004},
volume = {20},
number = {2},
pages = {229--242},
doi = {10.1109/TRA.2004.824649},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{ladd-kavraki2004using-motion-planning,
title = {Using Motion Planning for Knot Untangling},
author = {Ladd, A. M. and Kavraki, Lydia E},
journal = {International Journal of Robotics Research},
year = {2004},
volume = {23},
number = {7-8},
pages = {797--808},
doi = {10.1177/0278364904045469},
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.},
keyword = {other robotics}
}
@article{yao-kristensen2003accurate-sensitive-and,
title = {An Accurate, Sensitive, and Scalable Method to Identify Functional Sites in Protein
Structures},
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},
journal = {Journal of Molecular Biology},
year = {2003},
volume = {326},
number = {1},
pages = {255--261},
doi = {10.1016/S0022-2836(02)01336-0},
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.},
keyword = {functional annotation},
note = {PMID: 12547207}
}
@article{teodoro-phillips2003understanding-protein-flexibility,
title = {Understanding Protein Flexibility through Dimensionality Reduction},
author = {Teodoro, Miguel L. and {Phillips Jr.}, George N. and Kavraki, Lydia E},
journal = {Journal of Computational Biology},
year = {2003},
volume = {10},
number = {3-4},
pages = {617--634},
doi = {10.1089/10665270360688228},
abstract = {This work shows how to decrease the complexity of modeling flexibility in proteins
by reducing the number of dimensions necessary to model important macromolecular motions
such as the induced fit process. Induced fit occurs during the binding of a protein to other
proteins, nucleic acids or small molecules (ligands) and is a critical part of protein
function. It is now widely accepted that conformational changes of proteins can affect their
ability to bind other molecules and that any progress in modeling protein motion and
flexibility will contribute to the understanding of key biological functions. However,
modeling protein flexibility has proven a very difficult task. Experimental laboratory
methods such as X-ray crystallography produce rather limited information, while
computational methods such as Molecular Dynamics are too slow for routine use with large
systems. In this work we show how to use the Principal Component Analysis method, a
dimensionality reduction technique, to transform the original high-dimensional
representation of protein motion into a lower dimensional representation that captures the
dominant modes of motions of proteins. For a medium-sized protein this corresponds to
reducing a problem with a few thousand degrees of freedom to one with less than fifty.
Although there is inevitably some loss in accuracy, we show that we can obtain conformations
that have been observed in laboratory experiments, starting from different initial
conformations and working in a drastically reduced search space.},
keyword = {proteins and drugs},
note = {PMID: 12935348}
}
@article{teodoro-kavraki2003conformational-flexibility-models,
title = {Conformational Flexibility Models for the Receptor in Structure Based Drug Design},
author = {Teodoro, Miguel L. and Kavraki, Lydia E},
journal = {Current Pharmaceutical Design},
year = {2003},
volume = {9},
pages = {1419--1431},
doi = {10.2174/1381612033454595},
abstract = {The problem of incorporating protein flexibility in the routine in silico screening
of large databases of small chemical compounds is still an unsolved and hard problem. The
main reason behind this difficulty is the exponential explosion in computational complexity
due to the inclusion of the large number of degrees of freedom that represent the receptor
flexibility. In order to address this limitation several flexibility models for the receptor
have been developed which try to limit the number of additional model parameters. These
models can be roughly grouped divided into five different categories. These are the use of
soft receptors which relax energetic penalties due to steric clashes, the selection of a few
critical degrees of freedom in the receptor binding site, the use of multiple receptor
structures either individually or by combining them using an averaging scheme, the use of
modified molecular simulation methods, or the use of collective degrees of freedom as a new
basis of representation for protein flexibility. All these flexible receptor models strive
to balance an improvement in the accuracy of the docking predictions with an increase in
computational cost. In addition, other challenges such as the development of accurate
solvation models and scoring functions make the receptor flexibility problem even harder.},
keyword = {proteins and drugs},
note = {PMID: 12871062}
}
@article{zhang-kavraki2002new-method-for,
title = {A New Method for Fast and Accurate Derivation of Molecular Conformations},
author = {Zhang, M. and Kavraki, Lydia E},
journal = {Journal of Chemical Information and Computer Sciences},
year = {2002},
volume = {42},
number = {1},
pages = {64--70},
doi = {10.1021/ci010327z},
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.},
keyword = {fundamentals of protein modeling},
note = {PMID: 11855967}
}
@article{agrawal-guibas2002algorithmic-issues-in,
title = {Algorithmic Issues in Modeling Motion},
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.},
journal = {ACM Computing Surveys},
year = {2002},
volume = {34},
number = {4},
pages = {550--572},
doi = {10.1145/592642.592647},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{yakey-lavalle2001randomized-path-planning,
title = {Randomized Path Planning for Linkages with Closed Kinematics Chains},
author = {Yakey, J. and LaValle, Steven M. and Kavraki, Lydia E},
journal = {IEEE Transactions on Robotics and Automation},
year = {2001},
volume = {17},
number = {6},
pages = {951--959},
doi = {10.1109/70.976030},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{lamiraux-kavraki2001positioning-of-symmetric,
title = {Positioning of Symmetric and Non-Symmetric Parts Using Radial and Constant Fields:
Computation of All Equilibrium Configurations},
author = {Lamiraux, F. and Kavraki, Lydia E},
journal = {International Journal of Robotics Research},
year = {2001},
volume = {20},
number = {8},
pages = {635--659},
doi = {10.1177/02783640122067589},
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.},
keyword = {other robotics}
}
@article{lamiraux-kavraki2001planning-paths-for,
title = {Planning Paths for Elastic Objects under Manipulation Constraints},
author = {Lamiraux, F. and Kavraki, Lydia E},
journal = {International Journal of Robotics Research},
year = {2001},
volume = {20},
number = {3},
pages = {188--208},
doi = {10.1177/02783640122067354},
keyword = {other robotics}
}
@article{lavalle-finn2000randomized-kinematics-based-approach,
title = {A Randomized Kinematics-based Approach to Pharmacophore-Constrained Conformational
Search and Database Screening},
author = {LaValle, Steven M. and Finn, Paul W. and Kavraki, Lydia E and Latombe, Jean-Claude},
journal = {Journal of Computational Chemistry},
year = {2000},
volume = {21},
number = {9},
pages = {731--747},
doi = {10.1002/(SICI)1096-987X(20000715)21:9<731::AID-JCC3>3.0.CO;2-R},
abstract = {Computational tools have greatly expedited the pharmaceutical drug design process in
recent years. One common task in this process is the search of a large library for small
molecules that can achieve both a low-energy conformation and a prescribed pharmacophore.
The pharmacophore expresses constraints on the 3D structure of the molecule by specifying
relative atom positions that should be maintained to increase the likelihood that the
molecule will bind with the receptor site. This paper presents a pharmacophore-based
database screening system that has been designed, implemented, and tested on a molecular
database. The primary focus of this paper is on a simple, randomized conformational search
technique that attempts to simultaneously reduce energy and maintain pharmacophore
constraints. This enables the identification of molecules in a database that are likely to
dock with a given protein, which can serve as a powerful aid in the search for better drug
candidates.},
keyword = {proteins and drugs}
}
@article{bohringer-donald2000part-orientation-with,
title = {Part Orientation with One or Two Stable Equilibria Using Programmable Vector Fields},
author = {Bohringer, K.-F. and Donald, B. R. and Kavraki, Lydia E and Lamiraux, F.},
journal = {IEEE Transactions on Robotics and Automation},
year = {2000},
volume = {16},
number = {2},
pages = {157--170},
doi = {10.1109/70.843172},
keyword = {other robotics}
}
@article{finn-kavraki1999computational-approaches-to,
title = {Computational Approaches to Drug Design},
author = {Finn, Paul W. and Kavraki, Lydia E},
journal = {Algorithmica},
year = {1999},
volume = {25},
pages = {347--371},
doi = {10.1007/PL00008282},
keyword = {proteins and drugs}
}
@article{kavraki-latombe1998randomized-query-processing,
title = {Randomized Query Processing in Robot Path Planning},
author = {Kavraki, Lydia E and Latombe, Jean-Claude and Motwani, R. and Raghavan, P.},
journal = {Journal of Computer and System Sciences},
month = aug,
year = {1998},
volume = {57},
number = {1},
pages = {50--60},
doi = {10.1006/jcss.1998.1578},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{kavraki-kolountzakis1998analysis-of-probabilistic,
title = {Analysis of Probabilistic Roadmaps for Path Planning},
author = {Kavraki, Lydia E and Kolountzakis, M. N. and Latombe, Jean-Claude},
journal = {IEEE Transactions on Robotics and Automation},
year = {1998},
volume = {14},
number = {1},
pages = {166--171},
doi = {10.1109/70.660866},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@article{finn-kavraki1998rapid-randomized-pharmacophore,
title = {{RAPID}: Randomized Pharmacophore Identification for drug design},
author = {Finn, Paul W. and Kavraki, Lydia E and Latombe, Jean-Claude and Shelton, C. and Venkat, S. and Yao, A.},
journal = {Computational Geometry: Theory and Applications},
year = {1998},
volume = {10},
number = {4},
pages = {263--272},
doi = {10.1016/S0925-7721(98)00008-X},
abstract = {This paper describes a randomized approach for finding invariants in a set of
flexible and chemically distinct ligands (drug molecules) that underlies an integrated
software system called RAPID currently under development. An invariant is a collection of
features embedded in Image3 which is present in one or more of the possible low-energy
conformations of each ligand. Such invariants are called pharmacophores and contain the
parts of the ligand that are primarily responsible for its binding with a receptor. The
identification of pharmacophores is crucial in drug design since frequently the structure of
targeted receptor is unknown but a number of molecules that interact with it have been
discovered by experiments. In these cases the pharmacophore is used as a template for
building more effective drugs. It is expected that our techniques and results will prove
useful in other applications such as molecular database screening and comparative molecular
field analysis.},
keyword = {proteins and drugs}
}
@article{barraquand-kavraki1997random-sampling-scheme,
title = {A Random Sampling Scheme for Robot Path Planning},
author = {Barraquand, B. and Kavraki, Lydia E and Latombe, Jean-Claude and Li, T.-Y. and Motwani, R. and Raghavan, P.},
journal = {International Journal of Robotics Research},
year = {1997},
volume = {16},
number = {6},
pages = {759--774},
doi = {10.1177/027836499701600604},
keyword = {fundamentals of sampling-based motion planning}
}
@article{kavraki-svestka1996probabilistic-roadmaps-for,
title = {Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces},
author = {Kavraki, Lydia E and {\v{S}}vestka, P. and Latombe, Jean-Claude and Overmars, M.},
journal = {IEEE Transactions on Robotics and Automation},
year = {1996},
volume = {12},
number = {4},
pages = {566--580},
doi = {10.1109/70.508439},
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)},
keyword = {fundamentals of sampling-based motion planning}
}
@article{wilson-kavraki1995two-handed-assembly-sequencing,
title = {Two-Handed Assembly Sequencing},
author = {Wilson, R. H. and Kavraki, Lydia E and Latombe, Jean-Claude and Lozano-Perez, Tomas},
journal = {International Journal of Robotics Research},
year = {1995},
volume = {14},
number = {4},
pages = {335--350},
doi = {10.1177/027836499501400403},
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.},
keyword = {other robotics}
}
@article{kavraki1995computation-of-configuration,
title = {Computation of Configuration Space Obstacles Using the Fast {F}ourier Transform},
author = {Kavraki, Lydia E},
journal = {IEEE Transactions on Robotics and Automation},
year = {1995},
volume = {11},
number = {3},
pages = {408--413},
doi = {10.1109/70.388783},
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.},
keyword = {other robotics}
}
@article{kavraki-kolountzakis1995partitioning-assembly-into,
title = {Partitioning an Assembly into Connected Parts is NP-hard},
author = {Kavraki, Lydia E and Kolountzakis, M. N.},
journal = {Information Processing Letters},
year = {1995},
volume = {55},
pages = {159--165},
doi = {10.1016/0020-0190(95)00083-O},
keyword = {other robotics}
}
@article{kavraki-latombe1993on-complexity-of,
title = {On the Complexity of Assembly Partitioning},
author = {Kavraki, Lydia E and Latombe, Jean-Claude and Wilson, R. H.},
journal = {Information Processing Letters},
year = {1993},
volume = {48},
number = {5},
pages = {229--235},
doi = {10.1016/0020-0190(93)90085-N},
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.},
keyword = {other robotics}
}
@incollection{elimelech2022-wafr-skills,
author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
main_auth = {1},
editor = {LaValle, Steven M. and O'Kane, Jason M. and Otte, Michael and Sadigh, Dorsa and Tokekar, Pratap},
title = {Automatic Cross-domain Task Plan Transfer by Caching Abstract Skills},
booktitle = {Algorithmic Foundations of Robotics XV},
pages = {470-487},
series = {Springer Proceedings in Advanced Robotics (SPAR)},
volume = {25},
publisher = {Springer International Publishing},
address = {Cham, Switzerland},
doi = {10.1007/978-3-031-21090-7_28},
isbn = {978-3-031-21090-7},
year = {2023},
abstract = {Solving realistic robotic task planning problems is computationally demanding. To
better exploit the planning effort and reduce the future planning cost, it is important to
increase the reusability of successful plans. To this end, we suggest a systematic and
automatable approach for plan transfer, by rethinking the plan caching procedure.
Specifically, instead of caching successful plans in their original domain, we suggest
transferring them upon discovery to a dynamically-defined abstract domain and cache them as
``abstract skills'' there. This technique allows us to maintain a unified, standardized, and
compact skill database, to avoid skill redundancy, and to support lifelong operation. Cached
skills can later be reconstructed into new domains on demand, and be applied to new tasks,
with no human intervention. This is made possible thanks to the novel concept of
``abstraction keys.'' An abstraction key, when coupled with a skill, provides all the
necessary information to cache it, reconstruct it, and transfer it across all domains in
which it is applicable---even domains we have yet to encounter. We practically demonstrate
the approach by providing two examples of such keys and explain how they can be used in a
manipulation planning domain.}
}
@incollection{elimelech2022-isrr-skills,
author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
main_auth = {1},
editor = {Billard, Aude and Asfour, Tamim and Khatib, Oussama},
title = {Efficient task planning using abstract skills and dynamic road map matching},
booktitle = {Robotics Research},
pages = {487–503},
series = {Springer Proceedings in Advanced Robotics (SPAR)},
volume = {27},
publisher = {Springer International Publishing},
address = {Cham, Switzerland},
doi = {10.1007/978-3-031-25555-7_33},
isbn = {978-3-031-25554-7},
year = {2023},
abstract = {Task planning is the problem of finding a discrete sequence of actions to achieve a
goal. Unfortunately, task planning in robotic domains is computationally challenging. To
address this, in our prior work, we explained how knowledge from a successful task solution
can be cached for later use, as an ``abstract skill." Such a skill is represented as a trace
of states (``road map") in an abstract space and can be matched with new tasks on-demand.
This paper explains how one can use a library of abstract skills, derived from past planning
experience, to reduce the computational cost of solving new task planning problems. As we
explain, matching a skill to a task allows us to decompose it into independent sub-tasks,
which can be quickly solved in parallel. This can be done automatically and dynamically
during planning. We begin by formulating this problem of ``planning with skills" as a
constraint satisfaction problem. We then provide a hierarchical solution algorithm, which
integrates with any standard task planner. Finally, we experimentally demonstrate the
computational benefits of the approach for reach-avoid tasks.}
}
@incollection{halperin2016robotics,
title = {Robotics},
author = {Halperin, D. and Kavraki, Lydia E and Solovey, Kiril},
booktitle = {Handbook of Discrete and Computational Geometry},
year = {2017},
address = {Boca Raton, NY},
editor = {Goodman, Jacob E. and O'Rourke, Joseph and T\'oth, Csaba D.},
keyword = {fundamentals of sampling-based motion planning},
publisher = {CRC Press},
url = {http://www.csun.edu/%7Ectoth/Handbook/HDCG3.html}
}
@incollection{kavraki-lavalle2016motion-planning,
title = {Motion Planning},
author = {Kavraki, Lydia E and LaValle, Steven M.},
booktitle = {Handbook of Robotics, 2nd Edition},
year = {2016},
doi = {10.1007/978-3-319-32552-1_7},
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.},
keyword = {fundamentals of sampling-based motion planning},
note = {(\url{http://www.bookmetrix.com/detail_full/book/bf39ef83-36b6-4bac-b546-a86864c58e19#downloads})},
publisher = {Springer}
}
@incollection{grady-bekris2011asynchronous-distributed-motion,
title = {Asynchronous Distributed Motion Planning with Safety Guarantees under Second-Order
Dynamics},
author = {Grady, Devin K and Bekris, Kostas E. and Kavraki, Lydia E},
booktitle = {Algorithmic Foundations of Robotics IX},
year = {2011},
volume = {68},
pages = {53--70},
doi = {10.1007/978-3-642-17452-0_4},
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.},
address = {Singapore, Singapore},
keyword = {kinodynamic systems},
publisher = {Springer Berlin / Heidelberg},
series = {Springer Tracts in Advanced Robotics}
}
@incollection{tsianos-halperin2008robot-algorithms,
title = {Robot Algorithms},
author = {Tsianos, Konstantinos I. and Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude},
booktitle = {Algorithms and Theory of Computation Handbook},
year = {2008},
volume = {2},
address = {Boca Raton, FL},
chapter = {4},
edition = {Second},
keyword = {fundamentals of sampling-based motion planning, other robotics},
publisher = {CRC Press}
}
@incollection{moll-schwarz2007roadmap-methods-for,
title = {Roadmap Methods for Protein Folding},
author = {Moll, Mark and Schwarz, D. and Kavraki, Lydia E},
booktitle = {Protein Structure Prediction: Methods and Protocols},
month = oct,
year = {2007},
doi = {10.1007/978-1-59745-574-9_9},
abstract = {Protein folding refers to the process whereby a protein assumes its intricate
three-dimensional shape. Different aspects of this problem have attracted much attention in
the last decade. Both experimental and computational methods have been used to study protein
folding and there has been considerable progress This chapter reviews a class of methods for
studying protein folding called roadmap methods. These methods are relatively new and are
still under active development. Roadmap methods are computational methods that have been
developed to understand the process or the mechanism by which a protein folds or unfolds. It
is typically assumed that the folded state is already known. Note that this is not a
comprehensive survey of all existing computational protein folding methods. In particular,
it does not cover Molecular Dynamics (MD) methods, Monte Carlo methods (MC), the use of
coarse grain models in simulations and many others.},
keyword = {proteins and drugs},
note = {PMID: 18075168},
publisher = {Humana Press}
}
@incollection{schwarz-kavraki2007protein-ligand-interactions-computational,
title = {Protein-Ligand Interactions: Computational Docking},
author = {Schwarz, D. and Kavraki, Lydia E},
booktitle = {Encyclopedia of Life Sciences},
year = {2007},
pages = {4105},
doi = {10.1002/9780470015902.a0004105},
abstract = {Protein{\textendash}ligand docking is the process of computationally predicting the
placement and binding affinity of a small organic molecule in the binding pocket of a
protein, usually for the purposes of drug discovery. A variety of techniques, ranging from
simple point-matching algorithms to explicit physical simulation methods have been developed
to address this problem.},
keyword = {proteins and drugs},
publisher = {Wiley}
}
@incollection{plaku-kavraki2007hybrid-systems-from,
title = {Hybrid Systems: From Verification to Falsification},
author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {International Conference on Computer Aided Verification (CAV)},
year = {2007},
volume = {4590},
pages = {468--481},
doi = {10.1007/978-3-540-73368-3_48},
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.},
address = {Berlin, Germany},
keyword = {planning from high-level specifications},
publisher = {Lecture Notes in Computer Science, Springer-Verlag Heidelberg}
}
@incollection{bekris-argyros2006exploiting-panoramic-vision,
title = {Exploiting Panoramic Vision for Angle-Based Robot Navigation},
author = {Bekris, Kostas E. and Argyros, A. A. and Kavraki, Lydia E},
booktitle = {Lecture Notes in Computer Science, Vol. 33},
year = {2006},
pages = {229--251},
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.},
keyword = {fundamentals of sampling-based motion planning, other robotics},
publisher = {Springer}
}
@incollection{ladd-kavraki2005fast-tree-based-exploration,
title = {Fast Tree-Based Exploration of State Space for Robots with Dynamics},
author = {Ladd, A. M. and Kavraki, Lydia E},
booktitle = {Algorithmic Foundations of Robotics VI},
year = {2005},
pages = {297--312},
doi = {10.1007/10991541_21},
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.},
keyword = {fundamentals of sampling-based motion planning, kinodynamic systems},
publisher = {Springer, STAR 17}
}
@incollection{akinc-bekris2005probabilistic-roadmaps-of,
title = {Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps},
author = {Akinc, M. and Bekris, Kostas E. and Chen, B. Y. and Ladd, A. M. and Plaku, E. and Kavraki, Lydia E},
booktitle = {Robotic Research: The Eleventh International Symposium},
year = {2005},
pages = {80--89},
doi = {10.1007/11008941_9},
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.},
keyword = {fundamentals of sampling-based motion planning},
publisher = {Springer, STAR 15}
}
@incollection{ladd-kavraki2004motion-planning-for,
title = {Motion Planning for Knot Untangling},
author = {Ladd, A. M. and Kavraki, Lydia E},
booktitle = {Algorithmic Foundations of Robotics V},
year = {2004},
pages = {7--23},
doi = {10.1007/b80173},
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.},
keyword = {other robotics},
publisher = {Springer Tracks in Advanced Robotics, Springer Verlag, STAR 7}
}
@incollection{halperin-kavraki2004robotics,
title = {Robotics},
author = {Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude},
booktitle = {Handbook of Discrete and Computational Geometry},
year = {2004},
pages = {1065--1094},
address = {Boca Raton, NY},
keyword = {fundamentals of sampling-based motion planning},
publisher = {CRC Press}
}
@incollection{teodoro-kavraki2002pharmacology,
title = {Pharmacology},
author = {Teodoro, Miguel L. and Kavraki, Lydia E},
booktitle = {Handbook of Data Mining and Knowledge Discovery},
month = jul,
year = {2002},
pages = {808--816},
editor = {Kl\"osgen, W. and \.Zytkow, J.},
keyword = {other biomedical computing},
publisher = {Oxford University Press}
}
@incollection{bohlin-kavraki2001randomized-algorithm-for,
title = {A Randomized Algorithm for Robot Path Planning Based on Lazy Evaluation},
author = {Bohlin, R. and Kavraki, Lydia E},
booktitle = {Handbook on Randomized Computing},
year = {2001},
pages = {221--249},
keyword = {fundamentals of sampling-based motion planning},
publisher = {Kluwer Academic Publishers}
}
@incollection{bohringer-donald2000distributed-universal-device,
title = {A Distributed, Universal Device for Planar Parts Feeding: Unique Part Orientation in
Programmable Vector Fields},
author = {Bohringer, K.-F. and Donald, B. R. and Kavraki, Lydia E and Lamiraux, F.},
booktitle = {Distributed Manipulation},
year = {2000},
pages = {1--29},
keyword = {other robotics},
publisher = {Kluwer Academic Publishers}
}
@incollection{kavraki1999algorithms-in-robotics,
title = {Algorithms in Robotics: The Motion Planning Perspective},
author = {Kavraki, Lydia E},
booktitle = {Frontiers of Engineering Publication},
year = {1999},
pages = {90--93},
keyword = {fundamentals of sampling-based motion planning},
publisher = {National Academy of Engineering}
}
@incollection{hsu-kavraki1999capturing-connectivity-of,
title = {Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable
Random Sampling Techniques},
author = {Hsu, David and Latombe, Jean-Claude and Motwani, R. and Kavraki, Lydia E},
booktitle = {Parallel and Distributed Processing},
year = {1999},
volume = {5},
pages = {159--182},
doi = {10.1007/978-1-4613-3282-4_8},
editor = {Pardalos, P.M. and Rajasekaran, S.},
isbn = {978-1-4613-3284-8},
keyword = {fundamentals of sampling-based motion planning},
publisher = {Springer, Boston, MA.}
}
@incollection{halperin-kavraki1999robot-algorithms,
title = {Robot Algorithms},
author = {Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude and Attalah, M.},
booktitle = {Algorithms and Theory of Computation Handbook},
year = {1999},
address = {Boca Raton, NY},
chapter = {21},
keyword = {fundamentals of sampling-based motion planning},
publisher = {CRC Press}
}
@incollection{bohringer-donald1999single-universal-force,
title = {A Single Universal Force Field can Uniquely Orient Non-Symmetric Parts},
author = {Bohringer, K.-F. and Donald, B. R. and Kavraki, Lydia E and Lamiraux, F.},
booktitle = {Robotics Research: The 9th International Symposium},
year = {1999},
pages = {395--402},
keyword = {other robotics},
publisher = {Springer}
}
@incollection{kavraki-latombe1998probabilistic-roadmaps-for,
title = {Probabilistic Roadmaps for Robot Path Planning},
author = {Kavraki, Lydia E and Latombe, Jean-Claude},
booktitle = {Practical Motion Planning in Robotics: Current Approaches and Future Directions},
year = {1998},
pages = {33--53},
keyword = {fundamentals of sampling-based motion planning},
publisher = {John Wiley}
}
@incollection{hsu-kavraki1998on-finding-narrow,
title = {On Finding Narrow Passages with Probabilistic Roadmap Planners},
author = {Hsu, David and Kavraki, Lydia E and Latombe, Jean-Claude and Motwani, R. and Sorkin, S.},
booktitle = {Robotics: The algorithmic perspective},
year = {1998},
pages = {141--153},
address = {Natick, MA},
keyword = {fundamentals of sampling-based motion planning},
publisher = {A.K. Peters},
url = {http://portal.acm.org/citation.cfm?id=298960.299001}
}
@incollection{kavraki1997geometry-and-discovery,
title = {Geometry and the Discovery of New Ligands},
author = {Kavraki, Lydia E},
booktitle = {Algorithms for Robotic Motion and Manipulation (WAFR 1996)},
year = {1997},
pages = {435--448},
keyword = {proteins and drugs},
publisher = {A.K. Peters}
}
@incollection{halperin-kavraki1997robotics,
title = {Robotics},
author = {Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude},
booktitle = {Handbook of Discrete and Computational Geometry},
year = {1997},
pages = {755--779},
address = {Boca Raton, NY},
keyword = {other robotics},
publisher = {CRC Press}
}
@inproceedings{elimelech2023-extract-skills,
title = {Extracting generalizable skills from a single plan execution using abstraction-critical
state detection},
author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
booktitle = {2023 International Conference on Robotics and Automation (ICRA)},
year = {2023},
month = may,
abstract = {Robotic task planning is computationally challenging. To reduce planning cost and
support life-long operation, we must leverage prior planning experience. To this end, we
address the problem of extracting reusable and generalizable abstract skills from successful
plan executions. In previous work, we introduced a supporting framework, allowing us,
theoretically, to extract an abstract skill from a single execution and later automatically
adapt it and reuse it in new domains. We also proved that, given a library of such skills,
we can significantly reduce the planning effort for new problems. Nevertheless, until now,
abstract-skill extraction could only be performed manually. In this paper, we finally close
the automation loop and explain how abstract skills can be practically and automatically
extracted. We start by analyzing the desired qualities of an abstract skill and formulate
skill extraction as an optimization problem. We then develop two extraction algorithms,
based on the novel concept of abstraction-critical state detection. As we show
experimentally, the approach is independent of any planning domain.}
}
@inproceedings{quintero2023-optimal-tmp,
title = {Optimal Grasps and Placements for Task and Motion Planning in Clutter},
author = {Quintero-Pe{\~n}a, Carlos and Kingston, Zachary and Pan, Tianyang and Shome, Rahul and Kyrillidis, Anastasios and Kavraki, Lydia E.},
booktitle = {2023 International Conference on Robotics and Automation (ICRA)},
year = {2023},
month = may,
abstract = {Many methods that solve robot planning problems, such as task and motion planners,
employ discrete symbolic search to find sequences of valid symbolic actions that are
grounded with motion planning. Much of the efficacy of these planners lies in this
grounding—bad placement and grasp choices can lead to inefficient planning when a problem
has many geometric constraints. Moreover, grounding methods such as naı̈ve sampling often
fail to find appropriate values for these choices in the presence of clutter. Towards
efficient task and motion planning, we present a novel optimization-based approach for
grounding to solve cluttered problems that have many constraints that arise from geometry.
Our approach finds an optimal grounding and can provide feedback to discrete search for more
effective planning. We demonstrate our method against baseline methods in complex simulated
environments.}
}
@inproceedings{sobti2023-temporal-task,
title = {Efficient Inference of Temporal Task Specifications from Human Demonstrations using
Experiment Design},
author = {Sobti, Shlok and Shome, Rahul and Kavraki, Lydia E.},
booktitle = {2023 International Conference on Robotics and Automation (ICRA)},
year = {2023},
month = may,
abstract = {Robotic deployments in human environments have motivated the need for autonomous
systems to be able to interact with humans and solve tasks effectively. Human demonstrations
of tasks can be used to infer underlying task specifications, commonly modeled with temporal
logic. State-of-the-art methods have developed Bayesian inference tools to estimate a
temporal logic formula from a sequence of demonstrations. The current work proposes the use
of experiment design to choose environments for humans to perform these demonstrations. This
reduces the number of demonstrations needed to estimate the unknown ground truth formula
with low error. A novel computationally efficient strategy is proposed to generate
informative environments by using an optimal planner as the model for the demonstrator.
Instead of evaluating all possible environments, the search space reduces to the placement
of informative orderings of likely eventual goals along an optimal planner’s solution. A
human study with 600 demonstrations from 20 participants for 4 tasks on a 2D interface
validates the proposed hypothesis and empirical performance benefit in terms of convergence
and error over baselines. The human study dataset is also publicly shared.}
}
@inproceedings{lee2023-simulation-actions,
title = {Object Reconfiguration with Simulation-Derived Feasible Actions},
author = {Lee, Yiyuan and Thomason, Wil and Kingston, Zachary and Kavraki, Lydia E.},
booktitle = {2023 International Conference on Robotics and Automation (ICRA)},
year = {2023},
month = may,
abstract = {3D object reconfiguration encompasses common robot manipulation tasks in which a set
of objects must be moved through a series of physically feasible state changes into a
desired final configuration. Object reconfiguration is challenging to solve in general, as
it requires efficient reasoning about environment physics that determine action validity.
This information is typically manually encoded in an explicit transition system.
Constructing these explicit encodings is tedious and error-prone, and is often a bottleneck
for planner use. In this work, we explore embedding a physics simulator within a motion
planner to implicitly discover and specify the valid actions from any state, removing the
need for manual specification of action semantics. Our experiments demonstrate that the
resulting simulation-based planner can effectively produce physically valid rearrangement
trajectories for a range of 3D object reconfiguration problems without requiring more than
an environment description and start and goal arrangements.}
}
@inproceedings{quintero2023-robotic-nurse,
title = {Robotic Tutors for Nurse Training: Opportunities for HRI Researchers},
author = {Quintero-Pe{\~n}a, Carlos and Qian, Peizhu and Fontenot, Nicole and Chen, Hsin-Mei and Hamlin, Shannan and Kavraki, Lydia and Unhelkar, Vaibhav},
booktitle = {AAAI Spring Symposia},
year = {2023}
}
@inproceedings{kingston2022-robowflex,
abstract = {Robowflex is a software library for robot motion planning in industrial and research
applications, leveraging the popular MoveIt library and Robot Operating System (ROS)
middleware. Robowflex takes advantage of the ease of motion planning with MoveIt while
providing an augmented API to craft and manipulate motion planning queries within a single
program. Robowflex's high-level API simplifies many common use-cases while still providing
access to the underlying MoveIt library. Robowflex is particularly useful for 1) developing
new motion planners, 2) evaluation of motion planners, and 3) complex problems that use
motion planning (e.g., task and motion planning). Robowflex also provides visualization
capabilities, integrations to other robotics libraries (e.g., DART and Tesseract), and is
complimentary to many other robotics packages. With our library, the user does not need to
be an expert at ROS or MoveIt in order to set up motion planning queries, extract
information from results, and directly interface with a variety of software components. We
provide a few example use-cases that demonstrate its efficacy.},
author = {Kingston, Zachary and Kavraki, Lydia E.},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
title = {Robowflex: Robot Motion Planning with MoveIt Made Easy},
year = {2022},
month = oct,
pages = {3108--3114},
doi = {10.1109/IROS47612.2022.9981698}
}
@inproceedings{ren2022-rearrangement,
abstract = {Robot manipulation in cluttered environments often requires complex and sequential
rearrangement of multiple objects in order to achieve the desired reconfiguration of the
target objects. Due to the sophisticated physical interactions involved in such scenarios,
rearrangement-based manipulation is still limited to a small range of tasks and is
especially vulnerable to physical uncertainties and perception noise. This paper presents a
planning framework that leverages the efficiency of sampling-based planning approaches, and
closes the manipulation loop by dynamically controlling the planning horizon. Our approach
interleaves planning and execution to progressively approach the manipulation goal while
correcting any errors or path deviations along the process. Meanwhile, our framework allows
the definition of manipulation goals without requiring explicit goal configurations,
enabling the robot to flexibly interact with all objects to facilitate the manipulation of
the target ones. With extensive experiments both in simulation and on a real robot, we
evaluate our framework on three manipulation tasks in cluttered environments: grasping,
relocating, and sorting. In comparison with two baseline approaches, we show that our
framework can significantly improve planning efficiency, robustness against physical
uncertainties, and task success rate under limited time budgets.},
author = {Ren, Kejia and Kavraki, Lydia E. and Hang, Kaiyu},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
title = {Rearrangement-Based Manipulation via Kinodynamic Planning and Dynamic Planning
Horizons},
year = {2022},
month = oct
}
@inproceedings{chamzas2022-contrastive-visual-task-planning,
title = {Comparing Reconstruction-and Contrastive-based Models for Visual Task Planning},
author = {Chamzas, Constantinos and Lippi, Martina and C. Welle, Michael and Varava, Anastasia and E. Kavraki, Lydia and Kragic, Danica},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
month = oct,
year = {2022},
abstract = {Learning state representations enables robotic planning directly from raw
observations such as images. Most methods learn state representations by utilizing losses
based on the reconstruction of the raw observations from a lower-dimensional latent space.
The similarity between observations in the space of images is often assumed and used as a
proxy for estimating similarity between the underlying states of the system. However,
observations commonly contain task-irrelevant factors of variation which are nonetheless
important for reconstruction, such as varying lighting and different camera viewpoints. In
this work, we define relevant evaluation metrics and perform a thorough study of different
loss functions for state representation learning. We show that models exploiting task
priors, such as Siamese networks with a simple contrastive loss, outperform
reconstruction-based representations in visual task planning.},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{quintero-chamzas2022-blind,
title = {Human-Guided Motion Planning in Partially Observable Environments},
author = {Quintero-Pe{\~n}a, Carlos and Chamzas, Constantinos and Sun, Zhanyi and Unhelkar, Vaibhav and Kavraki, Lydia E},
booktitle = {2022 International Conference on Robotics and Automation (ICRA)},
month = may,
year = {2022},
pages = {7226--7232},
doi = {10.1109/ICRA46639.2022.9811893},
abstract = {Motion planning is a core problem in robotics, with a range of existing methods
aimed to address its diverse set of challenges. However, most existing methods rely on
complete knowledge of the robot environment; an assumption that seldom holds true due to
inherent limitations of robot perception. To enable tractable motion planning for high-DOF
robots under partial observability, we introduce BLIND, an algorithm that leverages human
guidance. BLIND utilizes inverse reinforcement learning to derive motion-level guidance from
human critiques. The algorithm overcomes the computational challenge of reward learning for
high-DOF robots by projecting the robot’s continuous configuration space to a
motion-planner-guided discrete task model. The learned reward is in turn used as guidance to
generate robot motion using a novel motion planner. We demonstrate BLIND using the Fetch
robot an dperform two simulation experiments with partial observability. Our experiments
demonstrate that, despite the challenge of partial observability and high dimensionality,
BLIND is capable of generating safe robot motion and outperforms baselines on metrics of
teaching efficiency, success rate, and path quality.},
keyword = {uncertainty},
publisher = {IEEE}
}
@inproceedings{pan2022failing-execution,
title = {Failure is an option: Task and Motion Planning with Failing Executions},
author = {Pan, Tianyang and Wells, Andrew M. and Shome, Rahul and Kavraki, Lydia E.},
booktitle = {2022 International Conference on Robotics and Automation (ICRA)},
month = may,
year = {2022},
pages = {1947--1953},
doi = {10.1109/ICRA46639.2022.9812273},
abstract = {Future robotic deployments will require robots to be able to repeatedly solve a
variety of tasks in application domains. Task and motion planning addresses complex robotic
problems that combine discrete reasoning over states and actions and geometric interactions
during action executions. Moving beyond deterministic settings, stochastic actions can be
handled by modeling the problem as a Markov Decision Process. The underlying probabilities
however are typically hard to model since failures might be caused by hardware
imperfections, sensing noise, or physical interactions. We propose a framework to address a
task and motion planning setting where actions can fail during execution. To achieve a task
goal actions need to be computed and executed despite failures. The robot has to infer which
actions are robust and for each new problem effectively choose a solution that reduces
expected execution failures. The key idea is to continually recover and refine the
underlying beliefs associated with actions across multiple different problems in the domain.
Our proposed method can find solutions that reduce the expected number of discrete, executed
actions. Results in physics-based simulation indicate that our method outperforms baseline
replanning strategies to deal with failing executions},
keyword = {task and motion planning},
publisher = {IEEE}
}
@inproceedings{bansal2022-synthesis,
title = {Synthesis from Satisficing and Temporal Goals},
author = {Bansal, Suguman and Kavraki, Lydia E. and Vardi, Moshe V. and Wells, Andrew},
booktitle = {Proceedings of the AAAI Conference on Artifical Intelligence},
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.},
keyword = {planning from high-level specifications},
publisher = {AAAI}
}
@inproceedings{sobti2021-complex-motor-actions,
title = {{A Sampling-based Motion Planning Framework for Complex Motor Actions}},
author = {Sobti, Shlok and Shome, Rahul and Chaudhuri, Swarat and Kavraki, Lydia E.},
booktitle = {Proceedings of the {IEEE/RSJ} International Conference on Intelligent Robots and
Systems},
month = sep,
year = {2021},
pages = {6928--6934},
doi = {10.1109/IROS51168.2021.9636395},
abstract = {We present a framework for planning complex motor actions such as pouring or
scooping from arbitrary start states in cluttered real-world scenes. Traditional approaches
to such tasks use dynamic motion primitives (DMPs) learned from human demonstrations. We
enhance a recently proposed state-of-the-art DMP technique capable of obstacle avoidance by
including them within a novel hybrid framework. This complements DMPs with sampling-based
motion planning algorithms, using the latter to explore the scene and reach promising
regions from which a DMP can successfully complete the task. Experiments indicate that even
obstacle-aware DMPs suffer in task success when used in scenarios which largely differ from
the trained demonstration in terms of the start, goal, and obstacles. Our hybrid approach
significantly outperforms obstacle-aware DMPs by successfully completing tasks in cluttered
scenes for a pouring task in simulation. We further demonstrate our method on a real robot
for pouring and scooping tasks.},
keyword = {Motion and Path Planning, Manipulation Planning, Learning from Demonstration}
}
@inproceedings{kingston2021experience-foliations,
title = {Using Experience to Improve Constrained Planning on Foliations for Multi-Modal
Problems},
author = {Kingston, Zachary and Chamzas, Constantinos and Kavraki, Lydia E.},
booktitle = {{IEEE/RSJ} International Conference on Intelligent Robots and Systems},
month = sep,
year = {2021},
pages = {6922--6927},
doi = {10.1109/IROS51168.2021.9636236},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{wells2021-finite-horizon-synthesis,
title = {{Finite-Horizon Synthesis for Probabilistic Manipulation Domains}},
author = {Wells, Andrew M. and Kingston, Zachary and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},
booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation},
month = jun,
year = {2021},
pages = {6336--6342},
doi = {10.1109/ICRA48506.2021.9561297},
abstract = {Robots have begun operating and collaborating with humans in industrial and social
settings. This collaboration introduces challenges: the robot must plan while taking the
human’s actions into account. In prior work, the problem was posed as a 2-player
deterministic game, with a limited number of human moves. The limit on human moves is
unintuitive, and in many settings determinism is undesirable. In this paper, we present a
novel planning method for collaborative human-robot manipulation tasks via probabilistic
synthesis. We introduce a probabilistic manipulation domain that captures the interaction by
allowing for both robot and human actions with states that represent the configurations of
the objects in the workspace. The task is specified using Linear Temporal Logic over finite
traces (LTLf ). We then transform our manipulation domain into a Markov Decision Process
(MDP) and synthesize an optimal policy to satisfy the specification on this MDP. We present
two novel contributions: a formalization of probabilistic manipulation domains allowing us
to apply existing techniques and a comparison of different encodings of these domains. Our
framework is validated on a physical UR5 robot.},
keyword = {Synthesis, Probabilistic Systems}
}
@inproceedings{shome2021-bundle-of-edges,
title = {{Asymptotically Optimal Kinodynamic Planning Using Bundles of Edges}},
author = {Shome, Rahul and Kavraki, Lydia E.},
booktitle = {2021 IEEE International Conference on Robotics and Automation (ICRA)},
month = jun,
year = {2021},
pages = {9988--9994},
doi = {10.1109/ICRA48506.2021.9560836},
abstract = {Using sampling to estimate the connectivity of high-dimensional configuration spaces
has been the theoretical underpinning for effective sampling-based motion planners. Typical
strategies either build a roadmap, or a tree as the underlying search structure that
connects sampled configurations, with a focus on guaranteeing completeness and optimality as
the number of samples tends to infinity. Roadmap-based planners allow preprocessing the
space, and can solve multiple kinematic motion planning problems, but need a steering
function to connect pairwise-states. Such steering functions are difficult to define for
kinodynamic systems, and limit the applicability of roadmaps to motion planning problems
with dynamical systems. Recent advances in the analysis of single-query tree-based planners
has shown that forward search trees based on random propagations are asymptotically optimal.
The current work leverages these recent results and proposes a multi-query framework for
kinodynamic planning. Bundles of kinodynamic edges can be sampled to cover the state space
before the query arrives. Then, given a motion planning query, the connectivity of the state
space reachable from the start can be recovered from a forward search tree reasoning about a
local neighborhood of the edge bundle from each tree node. The work demonstrates
theoretically that considering any constant radial neighborhood during this process is
sufficient to guarantee asymptotic optimality. Experimental validation in five and twelve
dimensional simulated systems also highlights the ability of the proposed edge bundles to
express high-quality kinodynamic solutions. Our approach consistently finds higher quality
solutions compared to SST, and RRT, often with faster initial solution times. The strategy
of sampling kinodynamic edges is demonstrated to be a promising new paradigm.},
keyword = {Motion Planning, Asymptotic Optimality, Kinodynamic Planning, Bundle Of Edges}
}
@inproceedings{quintero2021-robust-motion-planning,
title = {{Robust Optimization-based Motion Planning for high-DOF Robots under Sensing
Uncertainty}},
author = {Quintero-Pe{\~n}a, Carlos and Kyrillidis, Anastasios and Kavraki, Lydia E.},
booktitle = {2021 IEEE International Conference on Robotics and Automation (ICRA)},
month = jun,
year = {2021},
pages = {9724--9730},
doi = {10.1109/ICRA48506.2021.9560917},
abstract = {Motion planning for high degree-of-freedom (DOF) robots is challenging, especially
when acting in complex environments under sensing uncertainty. While there is significant
work on how to plan under state uncertainty for low-DOF robots, existing methods cannot be
easily translated into the high-DOF case, due to the complex geometry of the robot's body
and its environment. In this paper, we present a method that enhances optimization-based
motion planners to produce robust trajectories for high-DOF robots for convex obstacles. Our
approach introduces robustness into planners that are based on sequential convex
programming: We reformulate each convex subproblem as a robust optimization problem that
``protects'' the solution against deviations due to sensing uncertainty. The parameters of
the robust problem are estimated by sampling from the distribution of noisy obstacles, and
performing a first-order approximation of the signed distance function. The original merit
function is updated to account for the new costs of the robust formulation at every step.
The effectiveness of our approach is demonstrated on two simulated experiments that involve
a full body square robot, that moves in randomly generated scenes, and a 7-DOF Fetch robot,
performing tabletop operations. The results show nearly zero probability of collision for a
reasonable range of the noise parameters for Gaussian and Uniform uncertainty.},
keyword = {uncertainty}
}
@inproceedings{chamzas2021-learn-sampling,
title = {{Learning Sampling Distributions Using Local 3D Workspace Decompositions for Motion
Planning in High Dimensions}},
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,
year = {2021},
pages = {1283--1289},
doi = {10.1109/ICRA48506.2021.9561104},
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.},
keyword = {fundamentals of sampling-based motion planning},
note = {(Top-4 finalist for best paper in Cognitive Robotics)},
url = {https://dx.doi.org/10.1109/ICRA48506.2021.9561104}
}
@inproceedings{pan2021multiple_manipulators,
title = {A General Task and Motion Planning Framework For Multiple Manipulators},
author = {Pan, Tianyang and Wells, Andrew M. and Shome, Rahul and Kavraki, Lydia E.},
booktitle = {{IEEE/RSJ} International Conference on Intelligent Robots and Systems},
year = {2021},
pages = {3168--3174},
doi = {10.1109/IROS51168.2021.9636119},
abstract = {Many manipulation tasks combine high-level discrete planning over actions with
low-level motion planning over continuous robot motions. Task and motion planning (TMP)
provides a powerful general framework to combine discrete and geometric reasoning, and
solvers have been previously proposed for single-robot problems. Multi-robot TMP expands the
range of TMP problems that can be solved but poses significant challenges when considering
scalability and solution quality. We present a general TMP framework designed for multiple
robotic manipulators. This is based on two contributions. First, we propose an optimal task
planner designed to support simultaneous discrete actions. Second, we introduce an
intermediate scheduler layer between task planner and motion planner to evaluate alternate
robot assignments to these actions. This aggressively explores the search space and
typically reduces the number of expensive task planning calls. Several benchmarks with a
rich set of actions for two manipulators are evaluated. We show promising results in
scalability and solution quality of our TMP framework with the scheduler for up to six
objects. A demonstration indicates scalability to up to five robots.},
keyword = {task and motion planning, multi-robot systems}
}
@inproceedings{moll2021hyperplan,
title = {{HyperPlan}: A Framework for Motion Planning Algorithm Selection and Parameter
Optimization},
author = {Moll, Mark and Chamzas, Constantinos and Kingston, Zachary and Kavraki, Lydia E.},
booktitle = {{IEEE/RSJ} Intl.\ Conf.\ on Intelligent Robots and Systems},
year = {2021},
pages = {2511--2518},
doi = {10.1109/IROS51168.2021.9636651},
abstract = {Over the years, many motion planning algorithms have been proposed. It is often
unclear which algorithm might be best suited for a particular class of problems. The problem
is compounded by the fact that algorithm performance can be highly dependent on parameter
settings. This paper shows that hyperparameter optimization is an effective tool in both
algorithm selection and parameter tuning over a given set of motion planning problems. We
present different loss functions for optimization that capture different notions of
optimality. The approach is evaluated on a broad range of scenes using two different
manipulators, a Fetch and a Baxter. We show that optimized planning algorithm performance
significantly improves upon baseline performance and generalizes broadly in the sense that
performance improvements carry over to problems that are very different from the ones
considered during optimization.},
}
@inproceedings{chamzas2020rep-learning,
title = {State Representations in Robotics: Identifying Relevant Factors of Variation using Weak
Supervision},
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},
month = dec,
year = {2020},
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.},
keyword = {other robotics},
url = {http://www.robot-learning.ml/2020/}
}
@inproceedings{butler2020,
title = {A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and
Maximum Constraints},
author = {Butler, Steven D. and Moll, Mark and Kavraki, Lydia E.},
booktitle = {Proceedings of Algorithmic Foundations of Robotics XII},
month = may,
year = {2020},
volume = {13},
pages = {368--383},
doi = {10.1007/978-3-030-43089-4_24},
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.},
editor = {Goldberg, K. and Abbeel, P. and Bekris, K. and Miller, L.},
publisher = {Springer}
}
@inproceedings{kingston2020weighting-multi-modal-leads,
title = {Informing Multi-Modal Planning with Synergistic Discrete Leads},
author = {Kingston, Zachary and Wells, Andrew M. and Moll, Mark and Kavraki, Lydia E.},
booktitle = {{IEEE} International Conference on Robotics and Automation},
year = {2020},
pages = {3199--3205},
doi = {10.1109/ICRA40945.2020.9197545},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{vidal2019online-multilayered-motion-planning,
title = {Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater
Vehicles},
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,
year = {2019},
pages = {8936--8942},
doi = {10.1109/ICRA.2019.8794009},
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.},
keyword = {planning from high-level specifications, kinodynamic systems},
note = {(Top-3 finalist for best student paper award)}
}
@inproceedings{hernandez2019lazy-evaluation-of-goal-specifications,
title = {Lazy Evaluation of Goal Specifications Guided by Motion Planning},
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,
year = {2019},
pages = {944--950},
doi = {10.1109/ICRA.2019.8793570},
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.},
keyword = {planning from high-level specifications, fundamentals of sampling-based motion
planning}
}
@inproceedings{he2019efficient-symbolic-reactive-synthesis-for-finite-horizon-tasks,
title = {Efficient Symbolic Reactive Synthesis for Finite-Horizon Tasks},
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,
year = {2019},
pages = {8993--8999},
doi = {10.1109/ICRA.2019.8794170},
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.},
keyword = {planning from high-level specifications},
note = {(Best paper award in Cognitive Robotics)}
}
@inproceedings{chamzas2019using-local-experiences-for-global-motion-planning,
title = {Using Local Experiences for Global Motion Planning},
author = {Chamzas, Constantinos and Shrivastava, Anshumali and Kavraki, Lydia E.},
booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation},
month = may,
year = {2019},
pages = {8606--8612},
doi = {10.1109/ICRA.2019.8794317},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{wang2018partial,
title = {Online Partial Conditional Plan Synthesis for POMDPs with Safe-Reachability
Objectives},
author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.},
booktitle = {Workshop on the Algorithmic Foundations of Robotics},
year = {2018},
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.},
keyword = {planning from high-level specifications; uncertainty}
}
@inproceedings{wang2018bounded-policy-synthesis,
title = {Bounded Policy Synthesis for {POMDP}s with Safe-Reachability Objectives},
author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.},
booktitle = {Proceedings of the 17th International Conference on Autonomous Agents and
Multiagent Systems},
year = {2018},
pages = {238--246},
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.},
acmid = {3237424},
address = {Stockholm, Sweden},
keyword = {planning from high-level specifications; uncertainty},
series = {AAMAS 2018},
url = {http://dl.acm.org/citation.cfm?id=3237383.3237424}
}
@inproceedings{he-lahijanian2017reactive-manipulation,
title = {Reactive Synthesis For Finite Tasks Under Resource Constraints},
author = {He, Keliang and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},
booktitle = {2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
month = sep,
year = {2017},
pages = {5326--5332},
doi = {10.1109/IROS.2017.8206426},
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.},
address = {Vancouver, BC},
keyword = {planning from high-level specifications},
publisher = {IEEE}
}
@inproceedings{kingston2017decoupling-constraints,
title = {Decoupling Constraints from Sampling-Based Planners},
author = {Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.},
booktitle = {Proceedings of the International Symposium of Robotics Research},
year = {2017},
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},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{baker2017robonaut-2-and-you,
title = {Robonaut 2 and You: Specifying and Executing Complex Operations},
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)},
year = {2017},
doi = {10.1109/ARSO.2017.8025204},
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},
keyword = {planning from high-level specifications}
}
@inproceedings{butler2016a-general-algorithm-for-time-optimal-trajectory,
title = {A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and
Maximum Constraints},
author = {Butler, Stephen and Moll, Mark and Kavraki, Lydia E.},
booktitle = {Proceedings of the Workshop on the Algorithmic Foundations of Robotics},
month = dec,
year = {2016},
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.},
keyword = {kinodynamic systems}
}
@inproceedings{wang2016task,
title = {Task and Motion Policy Synthesis as Liveness Games},
author = {Wang, Yue and Dantam, Neil T. and Chaudhuri, Swarat and Kavraki, Lydia E.},
booktitle = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2016},
pages = {536--540},
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.},
keyword = {planning from high-level specifications},
publisher = {AAAI},
url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13146}
}
@inproceedings{pokorny2016warrt,
title = {High-Dimensional Winding-Augmented Motion Planning with 2D Topological Task Projections
and Persistent Homology},
author = {Pokorny, Florian T. and Kragic, Danica and Kavraki, Lydia E. and Goldberg, Ken},
booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation},
year = {2016},
pages = {24--31},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{kim-pena2016an-evaluation-of-different-clustering-methods,
title = {An Evaluation of Different Clustering Methods and Distance Measures Used for Grouping
Metabolic Pathways},
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},
year = {2016},
pages = {115--122},
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.},
keyword = {metabolic networks}
}
@inproceedings{hernandez2016planning-feasible-and-safe-paths,
title = {Planning Feasible and Safe Paths Online for Autonomous Underwater Vehicles in Unknown
Environments},
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},
year = {2016},
pages = {1313--1320},
doi = {10.1109/IROS.2016.7759217},
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.},
keyword = {other robotics}
}
@inproceedings{dantam2016tmp,
title = {Incremental Task and Motion Planning: A Constraint-Based Approach},
author = {Dantam, Neil T. and Kingston, Zachary K. and Chaudhuri, Swarat and Kavraki, Lydia E.},
booktitle = {Robotics: Science and Systems},
year = {2016},
doi = {10.15607/RSS.2016.XII.002},
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.},
keyword = {planning from high-level specifications}
}
@inproceedings{novinskaya2015_guid_proj,
title = {Improving protein conformational sampling by using guiding projections},
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)},
month = nov,
year = {2015},
pages = {1272--1279},
doi = {10.1109/BIBM.2015.7359863},
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.},
keyword = {fundamentals of protein modeling}
}
@inproceedings{moll2015structure-guided-selection-of-specificity-determining,
title = {Structure-Guided Selection of Specificity Determining Positions in the Human Kinome},
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,
year = {2015},
pages = {21--28},
doi = {10.1109/BIBM.2015.7359650},
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.},
keyword = {functional annotation}
}
@inproceedings{he-lahijanian2015towards-manipulation-planning,
title = {Towards Manipulation Planning with Temporal Logic Specifications},
author = {He, Keliang and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},
booktitle = {Proceedings of the 2015 IEEE International Conference on Robotics and Automation
(ICRA)},
month = may,
year = {2015},
pages = {346--352},
doi = {10.1109/ICRA.2015.7139022},
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.},
address = {Seattle, WA},
keyword = {planning from high-level specifications},
publisher = {IEEE}
}
@inproceedings{lahijanian-almagor2015this-time-robot,
title = {This Time the Robot Settles for a Cost: A Quantitative Approach to Temporal Logic
Planning with Partial Satisfaction},
author = {Lahijanian, Morteza and Almagor, Shaull and Fried, Dror and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {Proceedings of The Twenty-Ninth AAAI Conference (AAAI-15)},
month = jan,
year = {2015},
pages = {3664--3671},
abstract = {The specification of complex motion goals through temporal logics is increasingly
favored in robotics to narrow the gap between task and motion planning. A major limiting
factor of such logics, however, is their Boolean satisfaction condition. To relax this
limitation, we introduce a method for quantifying the satisfaction of co-safe linear
temporal logic specifications, and propose a planner that uses this method to synthesize
robot trajectories with the optimal satisfaction value. The method assigns costs to
violations of specifications from user-defined proposition costs. These violation costs
define a distance to satisfaction and can be computed algorithmically using a weighted
automaton. The planner utilizes this automaton and an abstraction of the robotic system to
construct a product graph that captures all possible robot trajectories and their distances
to satisfaction. Then, a plan with the minimum distance to satisfaction is generated by
employing this graph as the high-level planner in a synergistic planning framework. The
efficacy of the method is illustrated on a robot with unsatisfiable specifications in an
office environment.},
address = {Austin, TX},
keyword = {uncertainty},
publisher = {AAAI},
url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/10001}
}
@inproceedings{voss-moll2015heuristic-approach-to,
title = {A Heuristic Approach to Finding Diverse Short Paths},
author = {Voss, Caleb and Moll, Mark and Kavraki, Lydia E},
booktitle = {IEEE International Conference on Robotics and Automation},
year = {2015},
pages = {4173--4179},
doi = {10.1109/ICRA.2015.7139774},
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.},
address = {Seattle, WA},
keyword = {other robotics}
}
@inproceedings{kingston2015lc3,
title = {Kinematically constrained workspace control via linear optimization},
author = {Kingston, Zachary and Dantam, Neil and Kavraki, Lydia E.},
booktitle = {Proceedings of the IEEE-RAS 15th International Conference on Humanoid Robots
(Humanoids)},
year = {2015},
pages = {758--764},
doi = {10.1109/HUMANOIDS.2015.7363455},
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.},
keyword = {other robotics}
}
@inproceedings{luna-lahijanian2014optimal-and-efficient,
title = {Optimal and Efficient Stochastic Motion Planning in Partially-Known Environments},
author = {Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E},
booktitle = {Proceedings of The Twenty-Eighth AAAI Conference on Artificial Intelligence},
month = jul,
year = {2014},
pages = {2549--2555},
abstract = {A framework capable of computing optimal control policies for a continuous system in
the presence of both action and environment uncertainty is presented in this work. The
framework decomposes the planning problem into two stages: an offline phase that reasons
only over action uncertainty and an online phase that quickly reacts to the uncertain
environment. Offline, a bounded-parameter Markov decision process (BMDP) is employed to
model the evolution of the stochastic system over a discretization of the environment.
Online, an optimal control policy over the BMDP is computed. Upon the discovery of an
unknown environment feature during policy execution, the BMDP is updated and the optimal
control policy is efficiently recomputed. Depending on the desired quality of the control
policy, a suite of methods is presented to incorporate new information into the BMDP with
varying degrees of detail online. Experiments confirm that the framework recomputes
high-quality policies in seconds and is orders of magnitude faster than existing methods.},
address = {Quebec City, Canada},
keyword = {uncertainty},
url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8457}
}
@inproceedings{luna-lahijanian2014fast-stochastic-motion,
title = {Fast Stochastic Motion Planning with Optimality Guarantees using Local Policy
Reconfiguration},
author = {Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E},
booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation},
month = may,
year = {2014},
pages = {3013--3019},
doi = {10.1109/ICRA.2014.6907293},
abstract = {This work presents a framework for fast reconfiguration of local control policies
for a stochastic system to satisfy a high-level task specification. The motion of the system
is abstracted to a class of uncertain Markov models known as bounded-parameter Markov
decision processes (BMDPs). During the abstraction, an efficient sampling-based method for
stochastic optimal control is used to construct several policies within a discrete region of
the state space in order for the system to transit between neighboring regions. A BMDP is
then used to find an optimal strategy over the local policies by maximizing a continuous
reward function; a new policy can be computed quickly if the reward function changes. The
efficacy of the framework is demonstrated using a sequence of online tasks, showing that
highly desirable policies can be obtained by reconfiguring existing local policies in just a
few seconds.},
address = {Hong Kong, China},
keyword = {uncertainty}
}
@inproceedings{lahijanian-kavraki2014sampling-based-strategy-planner,
title = {A Sampling-Based Strategy Planner for Nondeterministic Hybrid Systems},
author = {Lahijanian, Morteza and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {Proceedings of the International Conference on Robotics and Automation},
month = may,
year = {2014},
pages = {3005--3012},
doi = {10.1109/ICRA.2014.6907292},
abstract = {This paper introduces a strategy planner for nondeterministic hybrid systems with
complex continuous dynamics. The planner uses sampling-based techniques and game-theoretic
approaches to generate a series of plans and decision choices that increase the chances of
success within a fixed time budget. The planning algorithm consists of two phases:
exploration and strategy improvement. During the exploration phase, a search tree is grown
in the hybrid state space by sampling state and control spaces for a fixed amount of time.
An initial strategy is then computed over the search tree using a game-theoretic approach.
To mitigate the effects of nondeterminism in the initial strategy, the strategy improvement
phase extends new tree branches to the goal, using the data that is collected in the first
phase. The efficacy of this planner is demonstrated on simulation of two hybrid and
nondeterministic car-like robots in various environments. The results show significant
increases in the likelihood of success for the strategies computed by the two-phase
algorithm over a simple exploration planner.},
address = {Hong Kong, China},
keyword = {uncertainty},
publisher = {IEEE}
}
@inproceedings{luna-lahijanian2014asymptotically-optimal-stochastic,
title = {Asymptotically Optimal Stochastic Motion Planning with Temporal Goals},
author = {Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E},
booktitle = {Proceedings of the Workshop on the Algorithmic Foundations of Robotics},
month = mar,
year = {2014},
doi = {10.1007/978-3-319-16595-0_20},
abstract = {This work presents a planning framework that allows a robot with stochastic action
uncertainty to achieve a high-level task given in the form of a temporal logic formula. The
objective is to quickly compute a feedback control policy to satisfy the task specification
with maximum probability. A top-down framework is proposed that abstracts the motion of a
continuous stochastic system to a discrete, bounded- parameter Markov decision process
(bmdp), and then computes a control policy over the product of the bmdp abstraction and a
dfa representing the temporal logic specification. Analysis of the framework reveals that as
the resolution of the bmdp abstraction becomes finer, the policy obtained converges to
optimal. Simulations show that high-quality policies to satisfy complex temporal logic
specifications can be obtained in seconds, orders of magnitude faster than existing
methods.},
address = {Istanbul, Turkey},
keyword = {uncertainty}
}
@inproceedings{wang-wang2014active-planning-sensing,
title = {Active Planning, Sensing and Recognition Using a Resource-Constrained Discriminant
{POMDP}},
author = {Wang, Zhaowen and Wang, Zhangyang and Moll, Mark and Huang, Po-Sen and Grady, Devin K and Nasrabadi, Nasser and Huang, Thomas and Kavraki, Lydia E and Hasegawa-Johnson, Mark},
booktitle = {Proceedings of the IEEE/ISPRS Workshop on Multi-Sensor Fusion for Outdoor Dynamic
Scene Understanding at CVPR},
year = {2014},
doi = {10.1109/CVPRW.2014.116},
abstract = {In this paper, we address the problem of object class recognition via observations
from actively selected views/modalities/features under limited resource budgets. A Partially
Observable Markov Decision Process (POMDP) is employed to find optimal sensing and
recognition actions with the goal of long-term classification accuracy. Hetero- geneous
resource constraints {\textendash} such as motion, number of measurements and bandwidth
{\textendash} are explicitly modeled in the state variable, and a prohibitively high penalty
is used to prevent the violation of any resource constraint. To improve recognition
performance, we further incorporate discriminative classification models with POMDP, and
customize the reward function and observation model correspondingly. The proposed model is
validated on several data sets for multi-view, multi-modal vehicle classification and
multi-view face recognition, and demonstrates improvement in both recognition and resource
management over greedy methods and previous POMDP formulations.},
keyword = {uncertainty}
}
@inproceedings{nedunuri-prabhu2014smt-based-synthesis-of,
title = {{SMT}-Based Synthesis of Integrated Task and Motion Plans for Mobile Manipulation},
author = {Nedunuri, Srinivas and Prabhu, Sailesh and Moll, Mark and Chaudhuri, Swarat and Kavraki, Lydia E},
booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation},
year = {2014},
pages = {655--662},
doi = {10.1109/ICRA.2014.6906924},
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.},
keyword = {planning from high-level specifications}
}
@inproceedings{grady-moll2013combining-pomdp-abstraction,
title = {Combining a POMDP Abstraction with Replanning to Solve Complex, Position-Dependent
Sensing Tasks},
author = {Grady, Devin K and Moll, Mark and Kavraki, Lydia E},
booktitle = {Proceedings of the AAAI Fall Symposium},
month = nov,
year = {2013},
abstract = {The Partially-Observable Markov Decision Process (POMDP) is a general framework to
determine reward-maximizing action policies under noisy action and sensing conditions.
However, determining an optimal policy for POMDPs is often intractable for robotic tasks due
to the PSPACE-complete nature of the computation required. Several recent solvers have been
introduced that expand the size of problems that can be considered. Although these POMDP
solvers can respect complex motion constraints in theory, we show that the computational
cost does not provide a benefit in the eventual online execution, compared to our
alternative approach that relies on a policy that ignores some of the motion constraints. We
advocate using the POMDP framework where it is critical {\textendash} to find a policy that
provides the optimal action given all past noisy sensor observations, while abstracting some
of the motion constraints to reduce solution time. However, the actions of an abstract robot
are generally not executable under its true motion constraints. The problem is addressed
offline with a less-constrained POMDP, and navigation under the full system constraints is
handled online with replanning. We empirically demonstrate that the policy generated using
this abstracted motion model is faster to compute and achieves similar or higher reward than
addressing the motion constraints for a car-like robot as used in our experiments directly
in the POMDP.},
address = {Arlington, Virginia},
isbn = {978-1-57735-640-0},
keyword = {uncertainty},
publisher = {AAAI Press},
url = {https://www.aaai.org/ocs/index.php/FSS/FSS13/paper/view/7578}
}
@inproceedings{luna-sucan2013anytime-solution-optimization,
title = {Anytime Solution Optimization for Sampling-Based Motion Planning},
author = {Luna, Ryan and {\c S}ucan, Ioan A. and Moll, Mark and Kavraki, Lydia E},
booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation},
month = may,
year = {2013},
pages = {5053--5059},
doi = {10.1109/ICRA.2013.6631301},
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.},
address = {Karlsruhe, Germany},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{grady-moll2013automated-model-approximation,
title = {Automated Model Approximation for Robotic Navigation with {POMDP}s},
author = {Grady, Devin K and Moll, Mark and Kavraki, Lydia E},
booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation},
month = may,
year = {2013},
pages = {78--84},
doi = {10.1109/ICRA.2013.6630559},
abstract = {Partially-Observable Markov Decision Processes (POMDPs) are a problem class with
significant applicability to robotics when considering the uncertainty present in the real
world, however, they quickly become intractable for large state and action spaces. A method
to create a less complex but accurate action model approximation is proposed and evaluated
using a state-of-the-art POMDP solver. We apply this general and powerful formulation to a
robotic navigation task under state and sensing uncertainty. Results show that this method
can provide a useful action model that yields a policy with similar overall expected reward
compared to the true action model, often with significant computational savings. In some
cases, our reduced complexity model can solve problems where the true model is too complex
to find a policy that accomplishes the task. We conclude that this technique of building
problem-dependent approximations can provide significant computational advantages and can
help expand the complexity of problems that can be considered using current POMDP
techniques.},
address = {Karlsruhe, Germany},
keyword = {uncertainty},
publisher = {IEEE}
}
@inproceedings{maly-lahijanian2013iterative-temporal-motion,
title = {Iterative Temporal Motion Planning for Hybrid Systems in Partially Unknown
Environments},
author = {Maly, MR and Lahijanian, M and Kavraki, Lydia E and Kress-Gazit, H. and Vardi, Moshe Y.},
booktitle = {ACM International Conference on Hybrid Systems: Computation and Control (HSCC)},
month = apr,
year = {2013},
pages = {353--362},
doi = {10.1145/2461328.2461380},
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.},
address = {Philadelphia, PA, USA},
keyword = {planning from high-level specifications},
publisher = {ACM}
}
@inproceedings{gipson-moll2013resolution-independent-density,
title = {Resolution Independent Density Estimation for Motion Planning in High-Dimensional
Spaces},
author = {Gipson, B and Moll, Mark and Kavraki, Lydia E},
booktitle = {IEEE International Conference on Robotics and Automation},
year = {2013},
pages = {2429--2435},
doi = {10.1109/ICRA.2013.6630908},
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.},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{chyan-moll2013improving-prediction-of,
title = {Improving the Prediction of Kinase Binding Affinity Using Homology Models},
author = {Chyan, Jeffrey and Moll, Mark and Kavraki, Lydia E},
booktitle = {Proceedings of the Computational Structural Bioinformatics Workshop at the ACM
Conference on Bioinformatics, Computational Biology and Biomedical Informatics},
year = {2013},
doi = {10.1145/2506583.2506704},
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.},
address = {Washington, DC},
keyword = {functional annotation}
}
@inproceedings{grady-moll2012multi-robot-target-verification,
title = {Multi-Robot Target Verification with Reachability Constraints},
author = {Grady, Devin K and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E},
booktitle = {IEEE International Symposium on Safety, Security, and Rescue Robotics},
month = nov,
year = {2012},
pages = {1--6},
doi = {10.1109/SSRR.2012.6523873},
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.},
address = {College Station, TX},
isbn = {978-1-4799-0164-7},
keyword = {planning from high-level specifications, uncertainty},
publisher = {IEEE}
}
@inproceedings{grady-moll2012multi-objective-sensor-based-replanning,
title = {Multi-Objective Sensor-Based Replanning for a Car-Like Robot},
author = {Grady, Devin K and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E},
booktitle = {IEEE International Symposium on Safety, Security, and Rescue Robotics},
month = nov,
year = {2012},
pages = {1--6},
doi = {10.1109/SSRR.2012.6523898},
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.},
address = {College Station, TX},
isbn = {978-1-4799-0164-7},
keyword = {planning from high-level specifications, uncertainty},
publisher = {IEEE}
}