@article{fasoulis2024-apegen2,
title = {{APE-Gen2.0}: Expanding Rapid Class {I} Peptide-Major Histocompatibility Complex
Modeling to Post-Translational Modifications and Noncanonical Peptide Geometries},
author = {Fasoulis, Romanos and Rigo, Mauricio M. and Liz{\'e}e, Gregory and Antunes, Dinler A. and Kavraki, Lydia E.},
journal = {Journal of Chemical Information and Modeling},
year = {2024},
doi = {10.1021/acs.jcim.3c01667},
url = {https://pubs.acs.org/doi/10.1021/acs.jcim.3c01667},
month = mar,
pages = {1730-1750},
volume = {64},
issue = {5},
keywords = {Animals, *Peptides/chemistry, Major Histocompatibility Complex, Receptors, Antigen,
T-Cell/genetics/metabolism, Protein Processing, Post-Translational, *Hominidae/metabolism,
Protein Binding},
abstract = {The recognition of peptides bound to class I major histocompatibility complex
(MHC-I) receptors by T-cell receptors (TCRs) is a determinant of triggering the adaptive
immune response. While the exact molecular features that drive the TCR recognition are still
unknown, studies have suggested that the geometry of the joint peptide-MHC (pMHC) structure
plays an important role. As such, there is a definite need for methods and tools that
accurately predict the structure of the peptide bound to the MHC-I receptor. In the past few
years, many pMHC structural modeling tools have emerged that provide high-quality modeled
structures in the general case. However, there are numerous instances of non-canonical cases
in the immunopeptidome that the majority of pMHC modeling tools do not attend to, most
notably, peptides that exhibit non-standard amino acids and post-translational modifications
(PTMs) or peptides that assume non-canonical geometries in the MHC binding cleft. Such
chemical and structural properties have been shown to be present in neoantigens; therefore,
accurate structural modeling of these instances can be vital for cancer immunotherapy. To
this end, we have developed APE-Gen2.0, a tool that improves upon its predecessor and other
pMHC modeling tools, both in terms of modeling accuracy and the available modeling range of
non-canonical peptide cases. Some of the improvements include (i) the ability to model
peptides that have different types of PTMs such as phosphorylation, nitration, and
citrullination; (ii) a new and improved anchor identification routine in order to identify
and model peptides that exhibit a non-canonical anchor conformation; and (iii) a web server
that provides a platform for easy and accessible pMHC modeling. We further show that
structures predicted by APE-Gen2.0 can be used to assess the effects that PTMs have in
binding affinity in a more accurate manner than just using solely the sequence of the
peptide. APE-Gen2.0 is freely available at https://apegen.kavrakilab.org.}
}
@article{conev2024-hlaequity,
author = {Conev, Anja and Fasoulis, Romanos and Hall-Swan, Sarah and Ferreira, Rodrigo and Kavraki, Lydia E},
title = {{HLAEquity: Examining biases in pan-allele peptide-HLA binding predictors}},
journal = {iScience},
year = {2024},
month = jan,
volume = {27},
number = {1},
abstract = {Peptide-HLA (pHLA) binding prediction is essential in screening peptide candidates
for personalized peptide vaccines. Machine Learning (ML) pHLA binding prediction tools are
trained on vast amounts of data and are effective in screening peptide candidates. Most ML
models report generalizing to HLA alleles unseen during training (“pan-allele” models).
However, the use of datasets with imbalanced allele content raises concerns about biased
model performance. First, we examine the data bias of two ML-based pan-allele pHLA binding
predictors. We find that the pHLA datasets overrepresent alleles from geographic populations
of high-income countries. Second, we show that the identified data bias is perpetuated
within ML models, leading to algorithmic bias and subpar performance for alleles expressed
in low-income geographic populations. We draw attention to the potential therapeutic
consequences of this bias, and we challenge the use of the term “pan-allele” to describe
models trained with currently available public datasets.},
issn = {2589-0042},
doi = {10.1016/j.isci.2023.108613},
url = {https://doi.org/10.1016/j.isci.2023.108613},
eprint = {https://www.sciencedirect.com/science/article/pii/S2589004223026901}
}
@inproceedings{meng2024-review,
author = {Meng, Qingxi and Quintero-Pe{\~n}a, Carlos and Kingston, Zachary and Unhelkar, Vaibhav and Kavraki, Lydia E.},
title = {Perception-Aware Planning for Robotics: Challenges and Opportunities},
booktitle = {40th Anniversary of the IEEE International Conference on Robotics and Automation},
year = {2024},
abstract = {In this work, we argue that new methods are needed to generate robot motion for
navigation or manipulation while effectively achieving perception goals. We support our
argument by conducting experiments with a simulated robot that must accomplish a primary
task, such as manipulation or navigation, while concurrently monitoring an object in the
environment. Our preliminary study demonstrates that a decoupled approach fails to achieve
high success in either action-focused motion generation or perception goals, motivating
further developments of approaches that holistically consider both goals.}
}
@inproceedings{pan2024-iros,
author = {Pan, Tianyang and Verginis, Christos K. and Kavraki, Lydia E.},
title = {Robust and Safe Task-Driven Planning and Navigation for Heterogeneous Multi-Robot Teams
with Uncertain Dynamics},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
note = {To Appear.},
year = {2024},
abstract = {Task and motion planning (TAMP) can enhance intelligent multi-robot coordination.
TAMP becomes signifi- cantly more complicated in obstacle-cluttered environments and in the
presence of robot dynamic uncertainties. We propose a control framework that solves the
motion-planning problem for multi-robot teams with uncertain dynamics, addressing a key
component of the TAMP pipeline. The principal part of the proposed algorithm constitutes a
decentralized feedback control policy for tracking of reference paths taken by the robots
while avoiding collision and adapting in real time to the underlying dynamic uncertainties.
The proposed framework further leverages sampling-based motion planners to free the robots
from local-minimum configurations. Extensive exper- imental results in complex, realistic
environments illustrate the superior efficiency of the proposed approach, in terms of
planning time and number of encountered local minima, with respect to state-of-the-art
baseline methods.}
}
@inproceedings{ramsey2024-capt,
author = {Ramsey, Clayton W. and Kingston, Zachary and Thomason, Wil and Kavraki, Lydia E.},
booktitle = {Robotics: Science and Systems},
title = {Collision-Affording Point Trees: SIMD-Amenable Nearest Neighbors for Fast Collision
Checking},
year = {2024},
abstract = {Motion planning against sensor data is often a critical bottleneck in real-time
robot control. For sampling-based motion planners, which are effective for high-dimensional
systems such as manipulators, the most time-intensive component is collision checking. We
present a novel spatial data structure, the collision-affording point tree (CAPT): an exact
representation of point clouds that accelerates collision-checking queries between robots
and point clouds by an order of magnitude, with an average query time of less than 10
nanoseconds on 3D scenes comprising thousands of points. With the CAPT, sampling-based
planners can generate valid, high-quality paths in under a millisecond, with total
end-to-end computation time faster than 60 FPS, on a single thread of a consumer-grade CPU.
We also present a point cloud filtering algorithm, based on space-filling curves, which
reduces the number of points in a point cloud while preserving structure. Our approach
enables robots to plan at real-time speeds in sensed environments, opening up potential uses
of planning for high-dimensional systems in dynamic, changing, and unmodeled environments.}
}
@article{pan2024-tamper,
author = {Pan, Tianyang and Shome, Rahul and Kavraki, Lydia E.},
journal = {IEEE Transactions on Robotics},
title = {Task and Motion Planning for Execution in the Real},
year = {2024},
volume = {},
number = {},
pages = {1-16},
doi = {10.1109/TRO.2024.3418550},
abstract = {Task and motion planning represents a powerful set of hybrid planning methods that
combine reasoning over discrete task domains and continuous motion generation. Traditional
reasoning necessitates task domain models and enough information to ground actions to motion
planning queries. Gaps in this knowledge often arise from sources like occlusion or
imprecise modeling. This work generates task and motion plans that include actions cannot be
fully grounded at planning time. During execution, such an action is handled by a provided
human-designed or learned closed-loop behavior. Execution combines offline planned motions
and online behaviors till reaching the task goal. Failures of behaviors are fed back as
constraints to find new plans. Forty real-robot trials and motivating demonstrations are
performed to evaluate the proposed framework and compare against state-of-the-art. Results
show faster execution time, less number of actions, and more success in problems where
diverse gaps arise. The experiment data is shared for researchers to simulate these
settings. The work shows promise in expanding the applicable class of realistic partially
grounded problems that robots can address.}
}
@article{fasoulis2024-transfer,
title = {Transfer learning improves pMHC kinetic stability and immunogenicity predictions},
journal = {ImmunoInformatics},
volume = {13},
pages = {100030},
year = {2024},
issn = {2667-1190},
doi = {10.1016/j.immuno.2023.100030},
url = {https://www.sciencedirect.com/science/article/pii/S2667119023000101},
author = {Fasoulis, Romanos and Rigo, Mauricio Menegatti and Antunes, Dinler Amaral and Paliouras, Georgios and Kavraki, Lydia E.},
keywords = {Transfer learning, Peptide-MHC, Machine learning, Peptide kinetic stability, Peptide
immunogenicity},
abstract = {The cellular immune response comprises several processes, with the most notable ones
being the binding of the peptide to the Major Histocompability Complex (MHC), the
peptide-MHC (pMHC) presentation to the surface of the cell, and the recognition of the pMHC
by the T-Cell Receptor. Identifying the most potent peptide targets for MHC binding,
presentation and T-cell recognition is vital for developing peptide-based vaccines and
T-cell-based immunotherapies. Data-driven tools that predict each of these steps have been
developed, and the availability of mass spectrometry (MS) datasets has facilitated the
development of accurate Machine Learning (ML) methods for class-I pMHC binding prediction.
However, the accuracy of ML-based tools for pMHC kinetic stability prediction and peptide
immunogenicity prediction is uncertain, as stability and immunogenicity datasets are not
abundant. Here, we use transfer learning techniques to improve stability and immunogenicity
predictions, by taking advantage of a large number of binding affinity and MS datasets. The
resulting models, TLStab and TLImm, exhibit comparable or better performance than
state-of-the-art approaches on different stability and immunogenicity test sets
respectively. Our approach demonstrates the promise of learning from the task of peptide
binding to improve predictions on downstream tasks. The source code of TLStab and TLImm is
publicly available at https://github.com/KavrakiLab/TL-MHC.}
}
@inproceedings{muvvala2024games,
author = {Muvvala, Karan and Wells, Andrew M. and Lahijanian, Mortez and Kavraki, Lydia E. and Vardi, Moshe Y.},
title = {Stochastic Games for Interactive Manipulation Domains},
year = {2024},
booktitle = {IEEE International Conference on Robotics and Automation},
abstract = {As robots become more prevalent, the complexity of robot-robot, robot-human, and
robot-environment interactions increases. In these interactions, a robot needs to consider
not only the effects of its own actions, but also the effects of other agents’ actions and
the possible interactions between agents. Previous works have considered reactive synthesis,
where the human/environment is modeled as a deterministic, adversarial agent; as well as
probabilistic synthesis, where the human/environment is modeled via a Markov chain. While
they provide strong theoretical frameworks, there are still many aspects of human-robot
interaction that cannot be fully expressed and many assumptions that must be made in each
model. In this work, we propose stochastic games as a general model for human-robot
interaction, which subsumes the expressivity of all previous representations. In addition,
it allows us to make fewer modeling assumptions and leads to more natural and powerful
models of interaction. We introduce the semantics of this abstraction and show how existing
tools can be utilized to synthesize strategies to achieve complex tasks with guarantees.
Further, we discuss the current computational limitations and improve the scalability by two
orders of magnitude by a new way of constructing models for PRISM-games.},
doi = {10.1109/ICRA57147.2024.10611623},
url = {https://ieeexplore.ieee.org/document/10611623}
}
@inproceedings{thomason2024vamp,
author = {Thomason, Wil and Kingston, Zachary and Kavraki, Lydia E.},
title = {Motions in Microseconds via Vectorized Sampling-Based Planning},
year = {2024},
booktitle = {IEEE International Conference on Robotics and Automation},
abstract = {Modern sampling-based motion planning algorithms typically take between hundreds of
milliseconds to dozens of seconds to find collision-free motions for high degree-of-freedom
problems. This paper presents performance improvements of more than 500x over the
state-of-the-art, bringing planning times into the range of microseconds and solution rates
into the range of kilohertz, without specialized hardware. Our key insight is how to exploit
fine-grained parallelism within sampling-based planners, providing generality-preserving
algorithmic improvements to any such planner and significantly accelerating critical
subroutines, such as forward kinematics and collision checking. We demonstrate our approach
over a diverse set of challenging, realistic problems for complex robots ranging from 7 to
14 degrees-of-freedom. Moreover, we show that our approach does not require high-power
hardware by also evaluating on a low-power single-board computer. The planning speeds
demonstrated are fast enough to reside in the range of control frequencies and open up new
avenues of motion planning research.},
doi = {10.1109/ICRA57147.2024.10611190},
url = {https://ieeexplore.ieee.org/document/10611190}
}
@inproceedings{quintero2024impdist,
author = {Quintero-Pe{\~n}a, Carlos and Thomason, Wil and Kingston, Zachary and Kyrillidis, Anastasios and Kavraki, Lydia E.},
title = {Stochastic Implicit Neural Signed Distance Functions for Safe Motion Planning under
Sensing Uncertainty},
year = {2024},
booktitle = {IEEE International Conference on Robotics and Automation},
abstract = {Motion planning under sensing uncertainty is critical for robots in unstructured
environments to guarantee safety for both the robot and any nearby humans. Most work on
planning under uncertainty does not scale to high-dimensional robots such as manipulators,
assumes simplified geometry of the robot or environment, or requires per-object knowledge of
noise. Instead, we propose a method that directly models sensor-specific aleatoric
uncertainty to find safe motions for high-dimensional systems in complex environments,
without exact knowledge of environment geometry. We combine a novel implicit neural model of
stochastic signed distance functions with a hierarchical optimization-based motion planner
to plan low-risk motions without sacrificing path quality. Our method also explicitly bounds
the risk of the path, offering trustworthiness. We empirically validate that our method
produces safe motions and accurate risk bounds and is safer than baseline approaches.},
doi = {10.1109/ICRA57147.2024.10610773},
url = {https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10610773}
}
@inproceedings{elimelech2024icra,
author = {Elimelech, Khen and Kingston, Zachary and Thomason, Wil and Vardi, Moshe Y. and Kavraki, Lydia E.},
title = {Accelerating long-horizon planning with affordance-directed dynamic grounding of
abstract skills},
year = {2024},
booktitle = {IEEE International Conference on Robotics and Automation},
abstract = {Long-horizon task planning is important for robot autonomy, especially as a
subroutine for frameworks such as Integrated Task and Motion Planning. However, task
planning is computationally challenging and struggles to scale to realistic problem
settings. We propose to accelerate task planning over an agent's lifetime by integrating
abstract strategies: a generalizable planning experience encoding introduced in earlier
work. In this work, we contribute a practical approach to planning with strategies by
introducing a novel formalism of planning in a strategy-augmented domain. We also introduce
and formulate the notion of a strategy's affordance, which indicates its predicted benefit
to the solution, and use it to guide the planning and strategy grounding processes.
Together, our observations yield an affordance-directed, lazy-search planning algorithm,
which can seamlessly compose strategies and actions to solve long-horizon planning problems.
We evaluate our planner in an object rearrangement domain, where we demonstrate performance
benefits relative to a state-of-the-art task planner.},
doi = {10.1109/ICRA57147.2024.10610486},
url = {https://ieeexplore.ieee.org/document/10610486}
}
@article{conev2023-engens,
author = {Conev, Anja and Rigo, Mauricio Menegatti and Devaurs, Didier and Fonseca, André Faustino and Kalavadwala, Hussain and de Freitas, Martiela Vaz and Clementi, Cecilia and Zanatta, Geancarlo and Antunes, Dinler Amaral and Kavraki, Lydia E},
title = {{EnGens: a computational framework for generation and analysis of representative
protein conformational ensembles}},
journal = {Briefings in Bioinformatics},
pages = {bbad242},
year = {2023},
month = jul,
abstract = {{Proteins are dynamic macromolecules that perform vital functions in cells. A
protein structure determines its function, but this structure is not static, as proteins
change their conformation to achieve various functions. Understanding the conformational
landscapes of proteins is essential to understand their mechanism of action. Sets of
carefully chosen conformations can summarize such complex landscapes and provide better
insights into protein function than single conformations. We refer to these sets as
representative conformational ensembles. Recent advances in computational methods have led
to an increase in the number of available structural datasets spanning conformational
landscapes. However, extracting representative conformational ensembles from such datasets
is not an easy task and many methods have been developed to tackle it. Our new approach,
EnGens (short for ensemble generation), collects these methods into a unified framework for
generating and analyzing representative protein conformational ensembles. In this work, we:
(1) provide an overview of existing methods and tools for representative protein structural
ensemble generation and analysis; (2) unify existing approaches in an open-source Python
package, and a portable Docker image, providing interactive visualizations within a Jupyter
Notebook pipeline; (3) test our pipeline on a few canonical examples from the literature.
Representative ensembles produced by EnGens can be used for many downstream tasks such as
protein–ligand ensemble docking, Markov state modeling of protein dynamics and analysis of
the effect of single-point mutations.}},
issn = {1477-4054},
doi = {10.1093/bib/bbad242},
url = {https://doi.org/10.1093/bib/bbad242},
eprint = {https://academic.oup.com/bib/advance-article-pdf/doi/10.1093/bib/bbad242/50837168/bbad242.pdf}
}
@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},
pages = {5772--5778},
doi = {10.1109/ICRA48891.2023.10161270},
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},
pages = {3707--3713},
doi = {10.1109/ICRA48891.2023.10161455},
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},
pages = {9764--9770},
doi = {10.1109/ICRA48891.2023.10160692},
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},
pages = {8104--8111},
doi = {10.1109/ICRA48891.2023.10160377},
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.}
}
@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{hall-swan2023pepsim,
author = {Hall-Swan, Sarah and Slone, Jared and Rigo, Mauricio M. and Antunes, Dinler A. and Lizée, Gregory and Kavraki, Lydia E.},
title = {PepSim: T-cell cross-reactivity prediction via comparison of peptide sequence and
peptide-HLA structure},
journal = {Frontiers in Immunology},
volume = {14},
year = {2023},
url = {https://www.frontiersin.org/articles/10.3389/fimmu.2023.1108303},
doi = {10.3389/fimmu.2023.1108303},
issn = {1664-3224},
abstract = {Introduction: Peptide-HLA class I (pHLA) complexes on the surface of tumor cells can
be targeted by cytotoxic T-cells to eliminate tumors, and this is one of the bases for
T-cell-based immunotherapies. However, there exist cases where therapeutic T-cells directed
towards tumor pHLA complexes may also recognize pHLAs from healthy normal cells. The process
where the same T-cell clone recognizes more than one pHLA is referred to as T-cell
cross-reactivity and this process is driven mainly by features that make pHLAs similar to
each other. T-cell cross-reactivity prediction is critical for designing T-cell-based cancer
immunotherapies that are both effective and safe. Methods: Here we present PepSim, a novel
score to predict T-cell cross-reactivity based on the structural and biochemical similarity
of pHLAs. Results and discussion: We show our method can accurately separate cross-reactive
from non-crossreactive pHLAs in a diverse set of datasets including cancer, viral, and
self-peptides. PepSim can be generalized to work on any dataset of class I peptide-HLAs and
is freely available as a web server at pepsim.kavrakilab.org.}
}
@inproceedings{quintana2023llm,
author = {Quintana, Felix and Treangen, Todd and Kavraki, Lydia},
title = {Leveraging Large Language Models for Predicting Microbial Virulence from Protein
Structure and Sequence},
year = {2023},
isbn = {9798400701269},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3584371.3612953},
doi = {10.1145/3584371.3612953},
abstract = {In the aftermath of COVID-19, screening for pathogens has never been a more relevant
problem. However, computational screening for pathogens is challenging due to a variety of
factors, including (i) the complexity and role of the host, (ii) virulence factor divergence
and dynamics, and (iii) population and community-level dynamics. Considering a potential
pathogen's molecular interactions, specifically individual proteins and protein interactions
can help pinpoint a potential protein of a given microbe to cause disease. However, existing
tools for pathogen screening rely on existing annotations (KEGG, GO, etc), making the
assessment of novel and unannotated proteins more challenging. Here, we present an
LLM-inspired approach that considers protein sequence and structure to predict protein
virulence. We present a two-stage model incorporating evolutionary features captured from
the DistilProtBert language model and protein structure in a graph convolutional network.
Our model performs better than sequence alone for virulence function when high-quality
structures are present, thus representing a path forward for virulence prediction of novel
and unannotated proteins.},
booktitle = {Proceedings of the 14th ACM International Conference on Bioinformatics,
Computational Biology, and Health Informatics}
}
@inproceedings{shome2023privacy,
author = {Shome, Rahul and Kingston, Zachary and Kavraki, Lydia E.},
title = {Robots as {AI} Double Agents: Privacy in Motion Planning},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2023},
abstract = {Robotics and automation are poised to change the landscape of home and work in the
near future. Robots are adept at deliberately moving, sensing, and interacting with their
environments. The pervasive use of this technology promises societal and economic payoffs
due to its capabilities - conversely, the capabilities of robots to move within and sense
the world around them is susceptible to abuse. Robots, unlike typical sensors, are
inherently autonomous, active, and deliberate. Such automated agents can become AI double
agents liable to violate the privacy of coworkers, privileged spaces, and other
stakeholders. In this work we highlight the understudied and inevitable threats to privacy
that can be posed by the autonomous, deliberate motions and sensing of robots. We frame the
problem within broader sociotechnological questions alongside a comprehensive review. The
privacy-aware motion planning problem is formulated in terms of cost functions that can be
modified to induce privacy-aware behavior - preserving, agnostic, or violating. Simulated
case studies in manipulation and navigation, with altered cost functions, are used to
demonstrate how privacy-violating threats can be easily injected, sometimes with only small
changes in performance (solution path lengths). Such functionality is already widely
available. This preliminary work is meant to lay the foundations for near-future, holistic,
interdisciplinary investigations that can address questions surrounding privacy in
intelligent robotic behaviors determined by planning algorithms.},
note = {To Appear}
}
@article{litsa2023spec2mol,
title = {An end-to-end deep learning framework for translating mass spectra to de-novo
molecules},
author = {Litsa, Eleni E and Chenthamarakshan, Vijil and Das, Payel and Kavraki, Lydia E},
journal = {Communications Chemistry},
volume = {6},
number = {1},
pages = {132},
year = {2023},
publisher = {Nature Publishing Group UK London},
doi = {10.1038/s42004-023-00932-3},
abstract = {Elucidating the structure of a chemical compound is a fundamental task in chemistry
with applications in multiple domains including drug discovery, precision medicine, and
biomarker discovery. The common practice for elucidating the structure of a compound is to
obtain a mass spectrum and subsequently retrieve its structure from spectral databases.
However, these methods fail for novel molecules that are not present in the reference
database. We propose Spec2Mol, a deep learning architecture for molecular structure
recommendation given mass spectra alone. Spec2Mol is inspired by the Speech2Text deep
learning architectures for translating audio signals into text. Our approach is based on an
encoder-decoder architecture. The encoder learns the spectra embeddings, while the decoder,
pre-trained on a massive dataset of chemical structures for translating between different
molecular representations, reconstructs SMILES sequences of the recommended chemical
structures. We have evaluated Spec2Mol by assessing the molecular similarity between the
recommended structures and the original structure. Our analysis showed that Spec2Mol is able
to identify the presence of key molecular substructures from its mass spectrum, and shows on
par performance, when compared to existing fragmentation tree methods particularly when test
structure information is not available during training or present in the reference
database.}
}
@article{bayraktar2023-rearrangement,
author = {Bayraktar, Servet B. and Orthey, Andreas and Kingston, Zachary and Toussaint, Marc and Kavraki, Lydia E.},
journal = {IEEE Robotics and Automation Letters},
title = {Solving Rearrangement Puzzles using Path Defragmentation in Factored State Spaces},
year = {2023},
volume = {},
number = {},
pages = {1-8},
doi = {10.1109/LRA.2023.3282788},
abstract = {Rearrangement puzzles are variations of rearrangement problems in which the elements
of a problem are potentially logically linked together. To efficiently solve such puzzles,
we develop a motion planning approach based on a new state space that is logically factored,
integrating the capabilities of the robot through factors of simultaneously manipulatable
joints of an object. Based on this factored state space, we propose less-actions RRT
(LA-RRT), a planner which optimizes for a low number of actions to solve a puzzle. At the
core of our approach lies a new path defragmentation method, which rearranges and optimizes
consecutive edges to minimize action cost. We solve six rearrangement scenarios with a Fetch
robot, involving planar table puzzles and an escape room scenario. LA-RRT significantly
outperforms the next best asymptotically-optimal planner by 4.01 to 6.58 times improvement
in final action cost.}
}
@inproceedings{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.}
}
@inproceedings{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.}
}
@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 = {2023 31st IEEE International Conference on Robot and Human Interactive
Communication (RO-MAN)},
year = {2023}
}
@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}
}
@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,
pages = {1145--1152},
doi = {10.1109/IROS47612.2022.9981599}
}
@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},
pages = {12550--12557},
doi = {10.1109/IROS47612.2022.9981533},
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}
}
@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}
}
@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},
month = jun,
year = {2022},
volume = {36},
doi = {10.1609/aaai.v36i9.21202},
pages = {9679--9686},
number = {9},
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{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}
}
@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}
}
@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}
}
@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)}
}
@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}
}
@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}
}
@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.}
}
@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}
}
@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/}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@techreport{lewis2019-how-much-do-unstated-problem-constraints,
title = {How Much Do Unstated Problem Constraints Limit Deep Robotic Reinforcement Learning?},
author = {Lewis II, W. Cannon and Moll, Mark and Kavraki, Lydia E.},
month = sep,
year = {2019},
doi = {10.25611/az5z-xt37},
abstract = {Deep Reinforcement Learning is a promising paradigm for robotic control which has
been shown to be capable of learning policies for high-dimensional, continuous control of
unmodeled systems. However, Robotic Reinforcement Learning currently lacks clearly defined
benchmark tasks, which makes it difficult for researchers to reproduce and compare against
prior work. "Reacher" tasks, which are fundamental to robotic manipulation, are commonly
used as benchmarks, but the lack of a formal specification elides details that are crucial
to replication. In this paper we present a novel empirical analysis which shows that the
unstated spatial constraints in commonly used implementations of Reacher tasks make it
dramatically easier to learn a successful control policy with Deep Deterministic Policy
Gradients (DDPG), a state-of-the-art Deep RL algorithm. Our analysis suggests that less
constrained Reacher tasks are significantly more difficult to learn, and hence that existing
de facto benchmarks are not representative of the difficulty of general robotic
manipulation.},
institution = {Rice University}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@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}
}
@inproceedings{maly-kavraki2012low-dimensional-projections-for,
title = {Low-Dimensional Projections for SyCLoP},
author = {Maly, MR and Kavraki, Lydia E},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
month = oct,
year = {2012},
pages = {420--425},
doi = {10.1109/IROS.2012.6386202},
abstract = {This paper presents an extension to SyCLoP, a multilayered motion planning framework
that has been shown to successfully solve high-dimensional problems with differen- tial
constraints. SyCLoP combines traditional sampling-based planning with a high-level
decomposition of the workspace through which it attempts to guide a low-level tree of
motions. We investigate a generalization of SyCLoP in which the high- level decomposition is
defined over a given low-dimensional projected subspace of the state space. We begin with a
manually-chosen projection to demonstrate that projections other than the workspace can
potentially work well. We then evaluate SyCLoP{\textquoteright}s performance with random
projections and projections determined from linear dimensionality reduction over elements of
the state space, for which the results are mixed. As we will see, finding a useful
projection is a difficult problem, and we conclude this paper by discussing the merits and
drawbacks of various types of projections.},
address = {Vilamoura, Algarve, Portugal},
keyword = {planning from high-level specifications}
}
@inproceedings{sucan-kavraki2012accounting-for-uncertainty,
title = {Accounting for Uncertainty in Simultaneous Task and Motion Planning Using Task Motion
Multigraphs},
author = {Sucan, Ioan Alexandru and Kavraki, Lydia E},
booktitle = {IEEE International Conference on Robotics and Automation},
month = may,
year = {2012},
pages = {4822--4828},
doi = {10.1109/ICRA.2012.6224885},
abstract = {This paper describes an algorithm that considers uncertainty while solving the
simultaneous task and motion planning (STAMP) problem. Information about uncertainty is
transferred to the task planning level from the motion planning level using the concept of a
task motion multigraph (TMM). TMMs were introduced in previous work to improve the
efficiency of solving the STAMP problem for mobile manipulators. In this work, Markov
Decision Processes are used in conjunction with TMMs to select sequences of actions that
solve the STAMP problem such that the resulting solutions have higher probability of
feasibility. Experimental evaluation indicates significantly improved probability of
feasibility for solutions to the STAMP problem, compared to algorithms that ignore
uncertainty information when selecting possible sequences of actions. At the same time, the
efficiency due to TMMs is largely maintained.},
address = {St. Paul},
keyword = {planning from high-level specifications, uncertainty}
}
@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}
}
@inproceedings{dhanik-mcmurray2012autodock-based-incremental-docking,
title = {AUTODOCK-based Incremental Docking Protocol to Improve Docking of Large Ligands},
author = {Dhanik, A. and McMurray, John S and Kavraki, Lydia E},
booktitle = {IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW)},
year = {2012},
pages = {48--55},
doi = {10.1109/BIBMW.2012.6470370},
abstract = {It is well known that computer-aided docking of large ligands, with many rotatable
bonds, is extremely difficult. AutoDock is a widely used docking program that can dock small
ligands, with upto 5 or 6 rotatable bonds, accurately and quickly. Docking of larger
ligands, however, is not very accurate and is computationally expensive. In this paper we
present an AutoDock-based incremental docking protocol which docks a large ligand to its
target protein in increments. A fragment of the large ligand is first chosen and then
docked. Best docked conformations are incrementally grown and docked again, and this process
is repeated until all the atoms of the ligand are docked. Each docking operation is
performed using AutoDock. However, in each docking operation only a small number of
rotatable bonds are allowed to rotate. We did a systematic docking study on a dataset of 73
protein-ligand complexes derived from the core set of PDBbind database. The number of
rotatable bonds in the ligands vary from 7 to 30. Docking experiments were done to evaluate
the docking performance of the incremental protocol in comparison to
AutoDock{\textquoteright}s standard protocol. Results from the study show that, on average
over the dataset, docking of large ligands using our incremental protocol is 23-fold
computationally faster than docking using AutoDock{\textquoteright}s standard protocol and
also has comparable or better accuracy. We propose that, for docking large ligands, our
incremental protocol can be used as an alternative to AutoDock{\textquoteright}s standard
protocol.},
address = {Philadelphia},
keyword = {proteins and drugs}
}
@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}
}
@inproceedings{grady-moll2011look-before-you,
title = {Look Before You Leap: Predictive Sensing and Opportunistic Navigation},
author = {Grady, Devin K and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E},
booktitle = {Workshop on Progress and Open Problems in Motion Planning at the IEEE/RSJ
International Conference on Intelligent Robots and Systems},
month = sep,
year = {2011},
abstract = {This paper describes a novel method for identifying multiple targets with multiple
robots in a partially known environment. Two main issues are addressed. The first relates to
the use of motion planning algorithms to determine whether robots can reach
{\textquoteleft}{\textquoteleft}good{\textquoteright}{\textquoteright} positions that offer
the most informative measurements. The second concerns the use of predictive sensing to
decide where sensor measurements should be taken. The problem is formulated similar to a
next-best-view problem with differential constraints on the robots{\textquoteright} motion,
with additional layers of complexity due to visual occlusions as well as navigational
obstacles. We propose a new distributed sensing strategy that exploits the structure of
image manifolds to predict the utility of the measurements at a given position. This
information is encoded in a cost map that guides a motion planning algorithm. Coordination
among robots is achieved by incorporating additional information in each
robot{\textquoteright}s cost map. A range of simulations indicates that our approach
outperforms current approaches and demonstrates the advantages of predictive sensing and
accounting for reachability constraints.},
address = {San Francisco},
keyword = {other robotics}
}
@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}
}
@inproceedings{dhanik-mcmurray2011on-modeling-peptidomimetics,
title = {On modeling peptidomimetics in complex with the SH2 domain of Stat3},
author = {Dhanik, A. and McMurray, John S and Kavraki, Lydia E},
booktitle = {33rd Annual International Conference of the IEEE Engineering in Medicine and
Biology Society (EMBC {\textquoteright}11)},
month = aug,
year = {2011},
pages = {3329--3332},
doi = {10.1109/IEMBS.2011.6090878},
abstract = {Signal transducer and activator of transcription3 (Stat3) plays a role in human
cancers. One of the main approaches towards inhibiting its activity is the development of
phosphopetides or peptidomimetics that competitively bind to the SH2 domain of Stat3. This
work reports, to the best of our knowledge, the first computational molecular docking study
to model all of the 142 peptidomimetics that mimic the Stat3 inhibitory pTyr-X-X-Glu motif.
We used the docking programs AUTODOCK and VINA to model SH2 domain-peptidomimetic complexes
and estimate their binding affinities. We obtained better screening accuracy using AUTODOCK
which ranked the most potent inhibitor as second highest. Experimental binding energy values
and scores from docking programs correlated poorly, confirming the limitations of many
current docking programs when dealing with ligands that have a large number of rotatable
bonds. Nevertheless, for close to 65\% of peptidomimetics, the structures of complexes
computed by AUTODOCK are in agreement with current understanding of the structures. Modeling
of the SH2 domain-peptidomimetic complexes is essential to better understand and design drug
compounds for curing cancer. Our study is an important first step forward towards that
goal.},
address = {Boston, Massachusetts, USA},
keyword = {proteins and drugs}
}
@inproceedings{sucan-kavraki2011on-advantages-of,
title = {On the Advantages of Using Task Motion Multigraphs for Efficient Mobile Manipulation},
author = {Sucan, Ioan Alexandru and Kavraki, Lydia E},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2011},
pages = {4621--4626},
doi = {10.1109/IROS.2011.6048260},
address = {San Francisco, CA},
keyword = {planning from high-level specifications}
}
@inproceedings{sucan-kavraki2011mobile-manipulation-encoding,
title = {Mobile Manipulation: Encoding Motion Planning Options Using Task Motion Multigraphs},
author = {Sucan, Ioan Alexandru and Kavraki, Lydia E},
booktitle = {IEEE International Conference on Robotics and Automation},
year = {2011},
pages = {5492--5498},
doi = {10.1109/ICRA.2011.5980212},
address = {Shanghai, China},
keyword = {planning from high-level specifications}
}
@inproceedings{moll-sucan2011teaching-motion-planning,
title = {Teaching Motion Planning Concepts to Undergraduate Students},
author = {Moll, Mark and Sucan, Ioan Alexandru and Bordeaux, Janice and Kavraki, Lydia E},
booktitle = {IEEE Workshop on Advanced Robotics and its Social Impacts},
year = {2011},
doi = {10.1109/ARSO.2011.6301976},
abstract = {Motion planning is a central problem in robotics. Although it is an engaging topic
for undergraduate students, it is difficult to teach, and as a result, the material is often
only covered at an abstract level. Deep learning could be achieved by having students
implement and test different algorithms. However, there is usually no time within a single
class to have students completely implement several motion planning algorithms as they
require the development of many lower-level data structures. We present an ongoing project
to develop a teaching module for robotic motion planning centered around an integrated
software environment. The module can be taught early in the undergraduate curriculum, after
students have taken an introductory programming class.},
keyword = {other robotics}
}
@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}
}
@inproceedings{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}
}
@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}
}
@inproceedings{bhatia-kavraki2010sampling-based-motion-planning,
title = {Sampling-Based Motion Planning with Temporal Goals},
author = {Bhatia, Amit and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {IEEE International Conference on Robotics and Automation},
month = may,
year = {2010},
pages = {2689--2696},
doi = {10.1109/ROBOT.2010.5509503},
abstract = {This paper presents a geometry-based, multi-layered synergistic approach to solve
motion planning problems for mobile robots involving temporal goals. The temporal goals are
described over subsets of the workspace (called propositions) using temporal logic. A
multi-layered synergistic framework has been proposed recently for solving planning problems
involving significant discrete structure. In this framework, a high-level planner uses a
discrete abstraction of the system and the exploration information to suggest feasible
high-level plans. A low-level sampling-based planner uses the physical model of the system,
and the suggested high-level plans, to explore the state-space for feasible solutions. In
this paper, we advocate the use of geometry within the above framework to solve motion
planning problems involving temporal goals. We present a technique to construct the discrete
abstraction using the geometry of the obstacles and the propositions defined over the
workspace. Furthermore, we show through experiments that the use of geometry results in
significant computational speedups compared to previous work. Traces corresponding to
trajectories of the system are defined employing the sampling interval used by the low-level
algorithm. The applicability of the approach is shown for second-order nonlinear robot
models in challenging workspace environments with obstacles, and for a variety of temporal
logic specifications.},
address = {Anchorage, Alaska},
isbn = {978-1-4244-5040-4},
keyword = {planning from high-level specifications},
publisher = {IEEE}
}
@inproceedings{sucan-kavraki2010on-implementation-of,
title = {On the Implementation of Single-Query Sampling-Based Motion Planners},
author = {Sucan, Ioan Alexandru and Kavraki, Lydia E},
booktitle = {IEEE International Conference on Robotics and Automation},
year = {2010},
pages = {2005--2011},
doi = {10.1109/ROBOT.2010.5509172},
address = {Anchorage, Alaska},
keyword = {fundamentals of sampling-based motion planning}
}
@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}
}
@inproceedings{bhatia-kavraki2010motion-planning-with,
title = {Motion Planning with Hybrid Dynamics and Temporal Goals},
author = {Bhatia, Amit and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {IEEE Conference on Decision and Control},
year = {2010},
pages = {1108--1115},
doi = {10.1109/CDC.2010.5717440},
abstract = {In this paper, we consider the problem of motion planning for mobile robots
involving discrete constraints on dynamics, and high-level temporal goals. The robot is
modeled as a nonlinear hybrid system with the discrete transitions modeling the discrete
constraints. We use a multi-layered synergistic framework that has been proposed recently
for solving planning problems involving hybrid systems and high-level temporal goals. A
high-level planner uses a user-defined discrete abstraction of the hybrid system as well as
exploration information to suggest high-level plans. A low-level sampling-based planner uses
the dynamics of the hybrid system and the suggested high-level plans to explore the
state-space for feasible solutions. In our previous work, we have proposed a geometry-based
approach for the construction of the discrete abstraction for the case when the robot is
modeled as a continuous system. Here, we extend the approach for the construction of the
discrete abstraction to the case when the robot is modeled as nonlinear hybrid system. To
use the resulting abstraction more efficiently, we also propose a lazy-search approach for
high-level planning that reduces the size of the search space by reusing previously
constructed high-level plans for initializing the search. The new techniques are tested
experimentally for second-order nonlinear hybrid robot models in challenging workspace
environments with obstacles and for a variety of temporal logic specifications.},
address = {Atlanta, GA},
keyword = {planning from high-level specifications},
publisher = {IEEE}
}
@inproceedings{sucan-kavraki2009on-performance-of,
title = {On the Performance of Random Linear Projections for Sampling-Based Motion Planning},
author = {Sucan, Ioan Alexandru and Kavraki, Lydia E},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
month = oct,
year = {2009},
pages = {2434--2439},
doi = {10.1109/IROS.2009.5354403},
address = {St. Louis},
keyword = {fundamentals of sampling-based motion planning}
}
@inproceedings{rusu-sucan2009real-time-perception-guided-motion,
title = {Real-Time Perception-Guided Motion Planning for a Personal Robot},
author = {Rusu, Radu Bogdan and Sucan, Ioan Alexandru and Gerkey, Brian P and Chitta, Sachin and Beetz, Michael and Kavraki, Lydia E},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
month = oct,
year = {2009},
pages = {4245--4252},
doi = {10.1109/IROS.2009.5354396},
address = {St. Louis},
keyword = {other robotics}
}
@inproceedings{sucan-kavraki2009kinodynamic-motion-planning,
title = {Kinodynamic Motion Planning by Interior-Exterior Cell Exploration},
author = {Sucan, Ioan Alexandru and Kavraki, Lydia E},
booktitle = {Algorithmic Foundation of Robotics VIII (Proceedings of Workshop on the Algorithmic
Foundations of Robotics)},
year = {2009},
volume = {57},
pages = {449--464},
doi = {10.1007/978-3-642-00312-7_28},
abstract = { This paper presents a kinodynamic motion planner, Kinodynamic Motion Planning by
Interior-Exterior Cell Exploration (KPIECE), specifically designed for systems with complex
dynamics, where physics-based simulation is necessary. A multiple-level grid-based
discretization is used to estimate the coverage of the state space. The coverage estimates
help the planner detect the less explored areas of the state space. The planner also keeps
track of the boundary of the explored region of the state space and focuses exploration on
the less covered parts of this boundary. Extensive experiments show KPIECE provides
computational gain over state-of-the-art methods and allows solving some harder, previously
unsolvable problems. A shared memory parallel implementation is presented as well. This
implementation provides better speedup than an embarrassingly parallel implementation by
taking advantage of the evolving multi-core technology.},
address = {Guanajuato, Mexico},
keyword = {kinodynamic systems},
publisher = {STAR}
}
@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}
}
@inproceedings{plaku-kavraki2009falsification-of-ltl,
title = {Falsification of {LTL} Safety Properties in Hybrid Systems},
author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {Proceedings of the Conference on Tools and Algorithms for the Construction and
Analysis of Systems (TACAS 2009)},
year = {2009},
doi = {10.1007/s10009-012-0233-2},
abstract = {This paper develops a novel computational method for the falsification of safety
properties specified by syntactically safe linear temporal logic (LTL) formulas φ for
hybrid systems with general nonlinear dynamics and input controls. The method is based on an
effective combination of robot motion planning and model checking. Experiments on a hybrid
robotic system benchmark with nonlinear dynamics show significant speedup over related work.
The experiments also indicate significant speedup when using minimized DFA instead of
non-minimized NFA, as obtained by standard tools, for representing the violating prefixes of
φ.},
address = {York, UK},
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}
}
@inproceedings{haspel-moll2009tracing-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},
booktitle = {IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW)},
year = {2009},
doi = {10.1109/BIBMW.2009.5332115},
abstract = {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 re- quire a large
number of calculations and are hard to apply to large-scale conformational motions. 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 three 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.},
address = {Washington, DC},
keyword = {proteins and drugs}
}
@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}
}
@inproceedings{tsianos-kavraki2008replanning-powerful-planning,
title = {Replanning: A powerful planning strategy for hard kinodynamic problems},
author = {Tsianos, Konstantinos I. and Kavraki, Lydia E},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
month = sep,
year = {2008},
pages = {1667--1672},
doi = {10.1109/IROS.2008.4650965},
abstract = { A series of kinodynamic sampling-based planners have appeared over the last decade
to deal with high dimen- sional problems for robots with realistic motion constraints. Yet,
offline sampling-based planners only work in static and known environments, suffer from
unbounded memory requirements and the produced paths tend to contain a lot of unnecessary
maneuvers. This paper describes an online replanning algo- rithm which is flexible and
extensible. Our results show that using a sampling-based planner in a loop, we can guide the
robot to its goal using a low dimensional navigation function. We obtain higher success
rates and shorter solution paths in a series of problems using only bounded memory.},
address = {Nice, France},
isbn = {978-1-4244-2058-2},
keyword = {kinodynamic systems}
}
@inproceedings{ricklin-ricklin-lichtsteiner2008novel-insights-into,
title = {Novel insights into target specificities and molecular mechanisms for two potent
complement evasion proteins from Staphylococcus aureus.},
author = {Ricklin, D. and Ricklin-Lichtsteiner, S.K. and Sfyroera, G. and Chen, H. and Tzekou, A. and Magotti, P. and Wu, Y-Q. and Garcia, B.L. and McWorther, W.J. and Haspel, N. and Kavraki, Lydia E and Geisbrecht, B. and Lambris, J.D.},
booktitle = {XXII International Complement Workshop},
month = aug,
year = {2008},
abstract = {Many pathogens target the complement system as part of their strategy of escaping
the immune system. In this context, the extracellular fibrinogen-binding protein (Efb) and
the Staphylococcal complement inhibitor (SCIN) from Staphylococcus aureus have been
recognized as exceptionally potent complement inhibitors. While both proteins interfere at
the level of C3 convertases, their molecular mechanisms and binding specificities are
clearly distinct. In view of the increasingly problematic infections with S. aureus and the
potential of microbial evasion proteins as templates for therapeutic complement inhibitors,
more details about their mode of action are urgently needed. Here we present extensive
molecular studies on the structure, interaction properties and binding specificities of Efb,
and show that its target spectrum is far greater than initially expected. In particular, we
found that its C-terminal domain (Efb-C) efficiently prevents the interaction of C3d with
complement receptor 2 and therefore may have direct consequences for the bridging to
adaptive immune responses. Using hydrogen/deuterium exchange mass spectrometry, we confirmed
the induction of conformational changes in C3 upon binding of Efb-C and demonstrate that
such changes may significantly alter the interaction pattern of C3b with a number of ligands
and regulators. Furthermore, we extended our characterization of the binding interface
between Efb-C and C3d based on structural, biophysical, and computational methods, which
identified additional key residues and showed that this important interaction is largely
driven by electrostatic forces. Finally, we show that SCIN not only interacts with the
assembled C3 convertase but also directly binds to C3b at an area distant from the Efb-C
binding site. Biophysical experiments confirmed that SCIN stabilizes the C3 convertase and
indicate that the inhibitor prevents cleavage but not the initial binding of native C3 to
the convertase.},
address = {Basel, Switzerland},
keyword = {proteins and drugs},
url = {http://www.akm.ch/ICW2008/}
}
@inproceedings{plaku-kavraki2008discrete-search-leading,
title = {Discrete Search Leading Continuous Exploration for Kinodynamic Motion Planning},
author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {Robotics: Science and Systems},
month = jun,
year = {2008},
pages = {326--333},
abstract = {This paper presents the Discrete Search Leading continuous eXploration (DSLX)
planner, a multi-resolution approach to motion planning that is suitable for challenging
problems involving robots with kinodynamic constraints. Initially the method decomposes the
workspace to build a graph that encodes the physical adjacency of the decomposed regions.
This graph is searched to obtain leads, that is, sequences of regions that can be explored
with sampling-based tree methods to generate solution trajectories. Instead of treating the
discrete search of the adjacency graph and the exploration of the continuous state space as
separate components, DSLX passes information from one to the other in innovative ways. Each
lead suggests what regions to explore and the exploration feeds back information to the
discrete search to improve the quality of future leads. Information is encoded in edge
weights, which indicate the importance of including the regions associated with an edge in
the next exploration step. Computation of weights, leads, and the actual exploration make
the core loop of the algorithm.
Extensive experimentation shows that DSLX is very versatile. The discrete search can
drastically change the lead to reflect new information allowing DSLX to find solutions even
when sampling-based tree planners get stuck. Experimental results on a variety of
challenging kinodynamic motion planning problems show computational speedups of two orders
of magnitude over other widely used motion planning methods.},
address = {Atlanta, Georgia},
keyword = {kinodynamic systems},
publisher = {MIT Press},
url = {http://www.roboticsproceedings.org/rss03/p40.html}
}
@inproceedings{plaku-kavraki2008impact-of-workspace,
title = {Impact of Workspace Decompositions on Discrete Search Leading Continuous Exploration
(DSLX) Motion Planning},
author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.},
booktitle = {IEEE International Conference on Robotics and Automation},
month = may,
year = {2008},
pages = {3751--3756},
doi = {10.1109/ROBOT.2008.4543786},
abstract = {We have recently proposed DSLX, a motion planner that significantly reduces the
computational time for solving challenging kinodynamic problems by interleaving continuous
state-space exploration with discrete search on a workspace decomposition. An important but
inadequately understood aspect of DSLX is the role of the workspace decomposition on the
computational efficiency of the planner. Understanding this role is important for successful
applications of DSLX to increasingly complex robotic systems. This work shows that the
granularity of the workspace decomposition directly impacts computational efficiency: DSLX
is faster when the decomposition is neither too fine- nor too coarse-grained. Finding the
right level of granularity can require extensive fine-tuning. This work demonstrates that
significant computational efficiency can instead be obtained with no fine-tuning by using
conforming Delaunay triangulations, which in the context of DSLX provide a natural workspace
decomposition that allows an efficient interplay between continuous state-space exploration
and discrete search. The results of this work are based on extensive experiments on DSLX
using grid, trapezoidal, and triangular decompositions of various granularities to solve
challenging first and second-order kinodynamic motion-planning problems.},
address = {Pasadena, CA},
keyword = {planning from high-level specifications}
}
@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}
}
@inproceedings{sucan-kruse2008reconfiguration-for-modular,
title = {Reconfiguration for modular robots using kinodynamic motion planning},
author = {Sucan, Ioan Alexandru and Kruse, Jonathan F. and Yim, Mark and Kavraki, Lydia E},
booktitle = {ASME -- Dynamic Systems and Control},
year = {2008},
doi = {10.1115/DSCC2008-2296},
address = {Ann Arbor, Michigan, USA},
keyword = {kinodynamic systems}
}
@inproceedings{sucan-kruse2008kinodynamic-motion-planning,
title = {Kinodynamic Motion Planning with Hardware Demonstrations},
author = {Sucan, Ioan Alexandru and Kruse, Jonathan F. and Yim, Mark and Kavraki, Lydia E},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2008},
pages = {1661--1666},
doi = {10.1109/IROS.2008.4650914},
abstract = {This paper provides proof-of-concept that state-of-the-art sampling-based motion
planners that are tightly integrated with a physics-based simulator can compute paths that
can be executed by a physical robotic system. Such a goal has been the subject of intensive
research during the last few years and reflects the desire of the motion planning community
to produce paths that are directly relevant to realistic mechanical systems and do not need
a huge post-processing step in order to be executed on a robotic platform. To evaluate this
approach, a recently developed motion planner is used to compute paths for a modular robot
constructed from seven modules. These paths are then executed on hardware and compared with
the paths predicted by the planner. For the system considered, the planner prediction and
the paths achieved by the physical robot match, up to small errors. This work reveals the
potential of modern motion planning research and its implications in the design and
operation of complex robotic platforms.},
address = {Nice, France},
keyword = {kinodynamic systems}
}
@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}
}
@inproceedings{moll-kavraki2008matching-of-structural,
title = {Matching of Structural Motifs Using Hashing on Residue Labels and Geometric Filtering
for Protein Function Prediction},
author = {Moll, Mark and Kavraki, Lydia E},
booktitle = {The Seventh Annual International Conference on Computational Systems Bioinformatics
(CSB2008)},
year = {2008},
pages = {157--168},
doi = {10.1142/9781848162648_0014},
abstract = {There is an increasing number of proteins with known structure but unknown function.
Determining their function would have a significant impact on understanding diseases and
designing new therapeutics. However, experimental protein function determination is
expensive and very time-consuming. Computational methods can facilitate function
determination by identifying proteins that have high structural and chemical similarity. Our
focus is on methods that determine binding site similarity. Although several such methods
exist, it still remains a challenging problem to quickly find all functionally-related
matches for structural motifs in large data sets with high specificity. In this context, a
structural motif is a set of 3D points annotated with physicochemical information that
characterize a molecular function. We propose a new method called LabelHash that creates
hash tables of $n$-tuples of residues for a set of targets. Using these hash tables, we can
quickly look up partial matches to a motif and expand those matches to complete matches. We
show that by applying only very mild geometric constraints we can find statistically
significant matches with extremely high specificity in very large data sets and for very
general structural motifs. We demonstrate that our method requires a reasonable amount of
storage when employing a simple geometric filter and further improves on the specificity of
our previous work while maintaining very high sensitivity. Our algorithm is evaluated on 20
homolog classes and a non-redundant version of the Protein Data Bank as our background data
set. We use cluster analysis to analyze why certain classes of homologs are more difficult
to classify than others. The LabelHash algorithm is implemented on a web server at
http://kavrakilab.org/labelhash/.},
keyword = {functional annotation},
url = {http://csb2008.org/csb2008papers/077Moll.pdf}
}
@inproceedings{moll-kavraki2008labelhash-flexible-and,
title = {LabelHash: A Flexible and Extensible Method for Matching Structural Motifs},
author = {Moll, Mark and Kavraki, Lydia E},
booktitle = {Automated Function Prediction / BioSapiens meeting (AFP-BioSapiens)},
year = {2008},
doi = {10.1038/npre.2008.2199.1},
keyword = {functional annotation},
note = {Available from Nature Precedings.}
}
@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}
}
@inproceedings{fofanov-chen2008statistical-model-to,
title = {A Statistical Model to Correct Systematic Bias Introduced by Algorithmic Thresholds in
Protein Structural Comparison Algorithms},
author = {Fofanov, Viacheslav Y. and Chen, B. Y. and Bryant, Drew H and Moll, Mark and Lichtarge, Olivier and Kavraki, Lydia E and Kimmel, Marek},
booktitle = {IEEE International Conference on Bioinformatics and Biomedicine (BIBM)},
year = {2008},
doi = {10.1109/BIBMW.2008.4686202},
abstract = {The identification of protein function is crucial to understanding cellular
processes and selecting novel proteins as drug targets. However, experimental methods for
determining protein function can be expensive and time-consuming. Protein partial structure
comparison methods seek to guide and accelerate the process of function determination by
matching characterized functional site representations, motifs, to substructures within
uncharacterized proteins, matches. One common difficulty of all protein structural
comparison techniques is the computational cost of obtaining a match. In an effort to
maintain practical efficiency, some algorithms employ efficient geometric threshold-based
searches to eliminate biologically irrelevant matches. Thresholds refine and accelerate the
method by limiting the number of potential matches that need to be considered. However,
because statistical models rely on the output of the geometric matching method to accurately
measure statistical significance, geometric thresholds can also artificially distort the
basis of statistical models, making statistical scores dependant on geometric thresholds and
potentially causing significant reductions in accuracy of the functional annotation method.
This paper proposes a point-weight based correction approach to quantify and model the
dependence of statistical scores to account for the systematic bias introduced by
heuristics. Using a benchmark dataset of 20 structural motifs, we show that the point-weight
correction procedure accurately models the information lost during the geometric comparison
phase, removing systematic bias and greatly reducing misclassification rates of functionally
related proteins, while maintaining specificity.},
address = {Philadelphia, PA},
keyword = {functional annotation}
}
@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}
}
@inproceedings{bekris-tsianos2007distributed-protocol-for,
title = {A Distributed Protocol for Safe Real-Time Planning of Communicating Vehicles with
Second-Order Dynamics},
author = {Bekris, Kostas E. and Tsianos, Konstantinos I. and Kavraki, Lydia E},
booktitle = {First International Conference on Robot Communication and Coordination (ROBOCOMM
07)},
month = oct,
year = {2007},
abstract = {This work deals with the problem of planning in real-time, collision-free motions
for multiple communicating vehicles that operate in the same, partially-observable
environment. A challenging aspect of this problem is how to utilize communication so that
vehicles do not reach states from which collisions cannot be avoided due to second-order
motion constraints. This paper provides a distributed communication protocol for real-time
planning that guarantees collision avoidance with obstacles and between vehicles. It can
also allow the retainment of a communication network when the vehicles operate as a
networked team. The algorithm is a novel integration of sampling-based motion planners with
message-passing protocols for distributed constraint optimization. Each vehicle uses the
motion planner to generate candidate feasible trajectories and the message-passing protocol
for selecting a safe and compatible trajectory. The existence of such trajectories is
guaranteed by the overall approach. Experiments on a distributed simulator built on a
cluster of processors confirm the safety properties of the approach in applications such as
coordinated exploration. Furthermore, the distributed protocol has better scalability
properties when compared against typical priority-based schemes.},
address = {Athens, Greece},
keyword = {kinodynamic systems}
}
@inproceedings{bekris-tsianos2007decentralized-planner-that,
title = {A Decentralized Planner that Guarantees the Safety of Communicating Vehicles with
Complex Dynamics that Replan Online},
author = {Bekris, Kostas E. and Tsianos, Konstantinos I. and Kavraki, Lydia E},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
month = oct,
year = {2007},
doi = {10.1109/IROS.2007.4399520},
abstract = {This paper considers the problem of coordinating multiple vehicles with kinodynamic
constraints that operate in the same partially-known environment. The vehicles are able to
communicate within limited range. Their objective is to avoid collisions between them and
with the obstacles, while the vehicles move towards their goals. An important issue of
real-time planning for systems with bounded acceleration is that inevitable collision states
must also be avoided. The focus of this paper is to guarantee safety despite the dynamic
constraints with a decentralized motion planning technique that employs only local
information. We propose a coordination framework that allows vehicles to generate and select
compatible sets of valid trajectories and prove that this scheme guarantees
collision-avoidance in the specified setup. The theoretical results have been also
experimentally confirmed with a distributed simulator where each vehicle replans online with
a sampling-based, kinodynamic motion planner and uses message-passing to communicate with
neighboring agents.},
address = {San Diego, CA},
keyword = {kinodynamic systems}
}
@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}
}
@inproceedings{bekris-kavraki2007greedy-but-safe,
title = {Greedy but Safe Replanning under Kinodynamic Constraints},
author = {Bekris, Kostas E. and Kavraki, Lydia E},
booktitle = {International Conference on Robotics and Automation},
month = apr,
year = {2007},
pages = {704--710},
doi = {10.1109/ROBOT.2007.363069},
abstract = {We consider motion planning problems for a vehicle with kinodynamic constraints,
where there is partial knowledge about the environment and replanning is required. We
present a new tree-based planner that explicitly deals with kinodynamic constraints and
addresses the safety issues when planning under finite computation times, meaning that the
vehicle avoids collisions in its evolving configuration space. In order to achieve good
performance we incrementally update a tree data-structure by retaining information from
previous steps and we bias the search of the planner with a greedy, yet probabilistically
complete state space exploration strategy. Moreover, the number of collision checks required
to guarantee safety is kept to a minimum. We compare our technique with alternative
approaches as a standalone planner and show that it achieves favorable performance when
planning with dynamics. We have applied the planner to solve a challenging replanning
problem involving the mapping of an unknown workspace with a non-holonomic platform.},
address = {Rome, Italy},
keyword = {kinodynamic systems},
publisher = {IEEE press}
}
@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}
}