Publications
2024
- M. Moll, “3D Dubins Paths for Underwater Vehicles,” in Proc. IEEE/MTS Oceans Conf., Halifax, Canada, 2024. To appear.
BibTeX
@inproceedings{moll2024-3d-dubins-paths-for-underwater-vehicles, abstract = "The dynamics of unmanned underwater vehicles (UUVs) impose significant constraints on the types of paths that can be followed. A number of motion models have been proposed that are inspired by the Dubins vehicle model. We have investigated two state-of-the-art models that ensure a bounded turning rate, bounded pitch angle, and (in one case) a bounded pitch change rate. We will show that these existing models can produce undesirable solutions (or even no solutions) between an initial and final pose of a UUV. Here, we present a new model that combines these two models, preserves the best features of both, and is empirically shown to connect any arbitrary start and goal pose. We also present results that show how the new model can be used as a local planner in sampling-based algorithms.", address = "Halifax, Canada", author = "Moll, Mark", booktitle = "Proc. IEEE/MTS Oceans Conf.", keywords = "Path planning, 3D Dubins, UUVs.", note = "To appear.", title = "{3D} {D}ubins Paths for Underwater Vehicles", year = "2024" }Abstract
The dynamics of unmanned underwater vehicles (UUVs) impose significant constraints on the types of paths that can be followed. A number of motion models have been proposed that are inspired by the Dubins vehicle model. We have investigated two state-of-the-art models that ensure a bounded turning rate, bounded pitch angle, and (in one case) a bounded pitch change rate. We will show that these existing models can produce undesirable solutions (or even no solutions) between an initial and final pose of a UUV. Here, we present a new model that combines these two models, preserves the best features of both, and is empirically shown to connect any arbitrary start and goal pose. We also present results that show how the new model can be used as a local planner in sampling-based algorithms.
2023
- M. Moll, “A General Framework for Remote Command and Control of Robots in Space,” in AIAA Scitech 2023 Forum, National Harbor, MD, 2023.
BibTeX
@inproceedings{moll2023a-general-framework-for-remote-command, abstract = "Future space missions are expected to be increasingly uncrewed and robots are expected to perform station keeping duties. The state of the art in robotics makes full autonomous operation at rigorous space safety standards extremely challenging. At the same time, the communication delay between robots in space and operators on earth makes traditional teleoperation painfully slow. We have developed a hardware-agnostic framework for remotely operating robots that bridges the gap between full autonomy and teleoperation. The framework provides parametrized, reusable building blocks (called behaviors) for performing robot operations such as opening doors, pressing buttons, and picking objects. When using these behaviors, an operator provides a few inputs and approves an automatically computed plan before it is executed. These behaviors can be combined into much more complex objectives that can encode fallback behaviors if a particular behavior fails or conditional behaviors that depend on user or sensor inputs.", address = "National Harbor, MD", author = "Moll, Mark", booktitle = "AIAA Scitech 2023 Forum", doi = "10.2514/6.2023-1069", month = jan, title = "A General Framework for Remote Command and Control of Robots in Space", year = "2023" }Abstract
Future space missions are expected to be increasingly uncrewed and robots are expected to perform station keeping duties. The state of the art in robotics makes full autonomous operation at rigorous space safety standards extremely challenging. At the same time, the communication delay between robots in space and operators on earth makes traditional teleoperation painfully slow. We have developed a hardware-agnostic framework for remotely operating robots that bridges the gap between full autonomy and teleoperation. The framework provides parametrized, reusable building blocks (called behaviors) for performing robot operations such as opening doors, pressing buttons, and picking objects. When using these behaviors, an operator provides a few inputs and approves an automatically computed plan before it is executed. These behaviors can be combined into much more complex objectives that can encode fallback behaviors if a particular behavior fails or conditional behaviors that depend on user or sensor inputs.
2021
- M. Moll, C. Chamzas, Z. Kingston, and L. E. Kavraki, “HyperPlan: A Framework for Motion Planning Algorithm Selection and Parameter Optimization,” in IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, 2021, pp. 2511–2518.
BibTeX
@inproceedings{moll2021hyperplan, 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.", author = "Moll, Mark and Chamzas, Constantinos and Kingston, Zachary and Kavraki, Lydia E.", booktitle = "{IEEE/RSJ} Intl.\ Conf.\ on Intelligent Robots and Systems", doi = "10.1109/IROS51168.2021.9636651", pages = "2511--2518", title = "{HyperPlan}: A Framework for Motion Planning Algorithm Selection and Parameter Optimization", year = "2021" }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.
2020
- J. D. Hernández, S. Sobti, A. Sciola, M. Moll, and L. E. Kavraki, “Increasing Robot Autonomy via Motion Planning and an Augmented Reality Interface,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 1017–1023, Apr. 2020.
BibTeX
@article{hernandez2020increasing-robot-autonomy-via-motion, 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.", author = "Hern{\'a}ndez, Juan David and Sobti, Shlok and Sciola, Anthony and Moll, Mark and Kavraki, Lydia E.", doi = "10.1109/LRA.2020.2967280", journal = "IEEE Robotics and Automation Letters", keywords = "Motion and path planning, virtual reality and interfaces", month = apr, number = "2", pages = "1017-1023", title = "Increasing Robot Autonomy via Motion Planning and an Augmented Reality Interface", volume = "5", year = "2020" }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.
- S. M. Kim, M. I. Peña, M. Moll, G. N. Bennett, and L. E. Kavraki, “Improving the organization and interactivity of metabolic pathfinding with precomputed pathways,” BMC Bioinformatics, vol. 21, no. 1, p. 13, Jan. 2020.
BibTeX
@article{kim2020improving-the-organization-and-interactivity-of-metabolic, 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. ", author = "Kim, Sarah M. and Pe{\~n}a, Matthew I. and Moll, Mark and Bennett, George N. and Kavraki, Lydia E.", doi = "10.1186/s12859-019-3328-x", journal = "BMC Bioinformatics", keywords = "metabolic pathfinding; precomputation; atom mapping; graph search", month = jan, number = "1", pages = "13", title = "Improving the organization and interactivity of metabolic pathfinding with precomputed pathways", volume = "21", year = "2020" }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.
- S. Butler, M. Moll, and L. E. Kavraki, “A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints,” in Algorithmic Foundations of Robotics XII, K. Goldberg, P. Abbeel, K. Bekris, and L. Miller, Eds. Springer, 2020, pp. 368–383.
BibTeX
@incollection{butler2020a-general-algorithm-for-time-optimal-trajectory, abstract = "This paper presents a new algorithm which generates time-optimal trajectories given a path as input. The algorithm improves on previous approaches by generically handling a broader class of constraints on the dynamics. It eliminates the need for heuristics to select trajectory segments that are part of the optimal trajectory through an exhaustive, but efficient search. We also present an algorithm for computing all achievable velocities at the end of a path given an initial range of velocities. This algorithm effectively computes bundles of feasible trajectories for a given path and is a first step toward a new generation of more efficient kinodynamic motion planning algorithms. We present results for both algorithms using a simulated WAM arm with a Barrett hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end effector velocity. The new algorithms are compared with a state-of-the-art alternative approach.", author = "Butler, Stephen and Moll, Mark and Kavraki, Lydia E.", booktitle = "Algorithmic Foundations of Robotics {XII}", doi = "10.1007/978-3-030-43089-4_24", editor = "Goldberg, Ken and Abbeel, Pieter and Bekris, Kostas and Miller, Lauren", pages = "368-383", publisher = "Springer", title = "A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints", year = "2020" }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.
- Z. Kingston, M. Moll, and L. E. Kavraki, “Decoupling Constraints from Sampling-Based Planners,” in Robotics Research (The 18th International Symposium ISRR), N. M. Amato, G. Hager, S. Thomas, and M. Torres-Torriti, Eds. Springer, 2020, pp. 913–928.
BibTeX
@incollection{kingston2017decoupling-constraints-from-sampling-based, 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.", author = "Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.", booktitle = "Robotics Research (The 18th International Symposium ISRR)", doi = "10.1007/978-3-030-28619-4_62", editor = "Amato, N. M. and Hager, G. and Thomas, S. and Torres-Torriti, M.", pages = "913--928", publisher = "Springer", title = "Decoupling Constraints from Sampling-Based Planners", year = "2020" }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.
- D. A. Antunes, J. R. Abella, S. Hall-Swan, D. Devaurs, A. Conev, M. Moll, G. Lizée, and L. E. Kavraki, “HLA-Arena: A customizable environment for the structural modeling and analysis of peptide-HLA complexes for cancer immunotherapy,” JCO Clinical Cancer Informatics, vol. 4, pp. 623–636, 2020.
BibTeX
@article{antunes2020hla-arena, 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 Modeler 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.", 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.", doi = "10.1200/CCI.19.00123", journal = "{JCO} Clinical Cancer Informatics", keywords = "Human leukocyte antigen (HLA); Peptide-HLA complex; Homology modeling; Molecular docking; Structural modeling; Structural analysis; Cancer immunotherapy", pages = "623--636", title = "{HLA-Arena}: A customizable environment for the structural modeling and analysis of peptide-{HLA} complexes for cancer immunotherapy", volume = "4", year = "2020" }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 Modeler 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.
- Z. Kingston, A. M. Wells, M. Moll, J. M. Badger, and L. E. Kavraki, “Informing Multi-Modal Planning with Synergistic Discrete Leads,” in IEEE Intl. Conf. on Robotics and Automation, 2020.
BibTeX
@inproceedings{kingston2020informing-multi-modal-planning-with, abstract = "Robotic manipulation problems are inherently continuous, but typically have underlying discrete structure, e.g., whether or not an object is grasped. This means many problems are multi-modal and in particular have a continuous infinity of modes. For example, in a pick-and-place manipulation domain, every grasp and placement of an object is a mode. Usually manipulation problems require the robot to transition into different modes, e.g., going from a mode with an object placed to another mode with the object grasped. To successfully find a manipulation plan, a planner must find a sequence of valid single-mode motions as well as valid transitions between these modes. Many manipulation planners have been proposed to solve tasks with multi-modal structure. However, these methods require mode-specific planners and fail to scale to very cluttered environments or to tasks that require long sequences of transitions. This paper presents a general layered planning approach to multi-modal planning that uses a discrete ``lead'' to bias search towards useful mode transitions. The difficulty of achieving specific mode transitions is captured online and used to bias search towards more promising sequences of modes. We demonstrate our planner on complex scenes and show that significant performance improvements are tied to both our discrete ``lead'' and our continuous representation.", author = "Kingston, Zachary and Wells, Andrew M. and Moll, Mark and Badger, Julia M. and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA40945.2020.9197545", title = "Informing Multi-Modal Planning with Synergistic Discrete Leads", year = "2020" }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.
- R. Luna, M. Moll, J. M. Badger, and L. E. Kavraki, “A Scalable Motion Planner for High-Dimensional Kinematic Systems,” Intl. J. of Robotics Research, vol. 39, no. 4, pp. 361–388, 2020.
BibTeX
@article{luna2020a-scalable-motion-planner-for-high-dimensional, 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.", author = "Luna, Ryan and Moll, Mark and Badger, Julia M. and Kavraki, Lydia E.", doi = "10.1177/0278364919890408", journal = "Intl.\ J.\ of Robotics Research", number = "4", pages = "361--388", title = "A Scalable Motion Planner for High-Dimensional Kinematic Systems", volume = "39", year = "2020" }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.
2019
- D. Devaurs, D. A. Antunes, S. Hall-Swan, N. Mitchell, M. Moll, G. Lizée, and L. E. Kavraki, “Using parallelized incremental meta-docking can solve the conformational sampling issue when docking large ligands to proteins,” BMC Molecular and Cell Biology, vol. 20, no. 1, p. 42, Sep. 2019.
BibTeX
@article{devaurs2019using-parallelized-incremental-meta-docking, 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.", 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", doi = "10.1186/s12860-019-0218-z", journal = "BMC Molecular and Cell Biology", keywords = "molecular docking; protein-ligand docking; protein-peptide docking; conformational sampling; scoring; parallelism; incremental protocol", month = sep, number = "1", pages = "42", title = "Using parallelized incremental meta-docking can solve the conformational sampling issue when docking large ligands to proteins", volume = "20", year = "2019" }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.
- Z. Kingston, M. Moll, and L. E. Kavraki, “Exploring Implicit Spaces for Constrained Sampling-Based Planning,” Intl. J. of Robotics Research, vol. 38, no. 10–11, pp. 1151–1178, Sep. 2019.
BibTeX
@article{kingston2019exploring-implicit-spaces-for-constrained, 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.", author = "Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.", doi = "10.1177/0278364919868530", journal = "Intl.\ J.\ of Robotics Research", keywords = "Constrained Planning, Manipulation Planning, Sampling-Based Motion Planning, Manifold Constraints, End-Effector Constraints, Loop Closure Constraints, Motion Planning", month = sep, number = "10--11", pages = "1151--1178", title = "Exploring Implicit Spaces for Constrained Sampling-Based Planning", volume = "38", year = "2019" }Abstract
We present a review and reformulation of manifold constrained sampling-based motion planning within a unifying framework, IMACS (Implicit MAnifold Configuration Space). IMACS enables a broad class of motion planners to plan in the presence of manifold constraints, decoupling the choice of motion planning algorithm and method for constraint adherence into orthogonal choices. We show that implicit configuration spaces defined by constraints can be presented to sampling-based planners by addressing two key fundamental primitives: sampling and local planning, and that IMACS preserves theoretical properties of probabilistic completeness and asymptotic optimality through these primitives. Within IMACS, we implement projection- and continutation-based methods for constraint adherence, and demonstrate the framework on a range of planners with both methods in simulated and realistic scenarios. Our results show that the choice of method for constraint adherence depends on many factors and that novel combinations of planners and methods of constraint adherence can be more effective than previous approaches. Our implementation of IMACS is open source within the Open Motion Planning Library and is easily extended for novel planners and constraint spaces.
- J. D. Hernández, M. Moll, and L. E. Kavraki, “Lazy Evaluation of Goal Specifications Guided by Motion Planning,” in IEEE Intl. Conf. on Robotics and Automation, 2019, pp. 944–950.
BibTeX
@inproceedings{hernandez2019lazy-evaluation-of-goal-specifications, abstract = "Nowadays robotic systems are expected to share workspaces and collaborate with humans. In such collaborative environments, an important challenge is to ground or establish the correct semantic interpretation of a human request. Once such an interpretation is available, the request must be translated into robot motion commands in order to complete the desired task. It is not unusual that a human request cannot be grounded to a unique interpretation, thus leading to an ambiguous request. A simple example is to ask a robot to ``put a cup on the table,'' when there are multiple cups available. In order to deal with this kind of ambiguous request, we propose a delayed or lazy variable grounding. The focus of this paper is a motion planning algorithm that, given goal regions that represent different valid groundings, lazily finds a feasible path to any one valid grounding. This algorithm includes a rewardpenalty strategy, which attempts to prioritize those goal regions that seem more promising to provide a solution. We validate our approach by solving requests with multiple valid alternatives in both simulation and real-world experiments.", author = "Hern{\'a}ndez, Juan David and Moll, Mark and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2019.8793570", month = may, pages = "944--950", title = "Lazy Evaluation of Goal Specifications Guided by Motion Planning", year = "2019" }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. It is not unusual that a human request cannot be grounded to a unique interpretation, thus leading to an ambiguous request. A simple example is to ask a robot to “put a cup on the table,” when there are multiple cups available. In order to deal with this kind of ambiguous request, we propose a delayed or lazy variable grounding. The focus of this paper is a motion planning algorithm that, given goal regions that represent different valid groundings, lazily finds a feasible path to any one valid grounding. This algorithm includes a rewardpenalty strategy, which attempts to prioritize those goal regions that seem more promising to provide a solution. We validate our approach by solving requests with multiple valid alternatives in both simulation and real-world experiments.
- E. Vidal Garcia, M. Moll, N. Palomeras, J. D. Hernández, M. Carreras, and L. Kavraki, “Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater Vehicles,” in IEEE Intl. Conf. on Robotics and Automation, 2019, pp. 8936–8942.
BibTeX
@inproceedings{vidal2019online-multilayered-motion-planning, abstract = "Underwater robots are subject to complex hydrodynamic forces. These forces define how the vehicle moves, so it is important to consider them when planning trajectories. However, performing motion planning considering the dynamics on the robot's onboard computer is challenging due to the limited computational resources available. In this paper an efficient motion planning framework for autonomous underwater vehicles (AUVs) 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 inevitable collision states (ICSs). Finally, we present simulations and experiments using a real underwater robot to demonstrate the capabilities of our framework.", author = "Vidal Garcia, Eduard and Moll, Mark and Palomeras, N. and Hern{\'a}ndez, Juan David and Carreras, Marc and Kavraki, Lydia", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2019.8794009", month = may, pages = "8936--8942", title = "Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater Vehicles", year = "2019" }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 autonomous underwater vehicles (AUVs) 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 inevitable collision states (ICSs). Finally, we present simulations and experiments using a real underwater robot to demonstrate the capabilities of our framework.
- E. E. Litsa, M. I. Peña, M. Moll, G. Giannakopoulos, G. N. Bennett, and L. E. Kavraki, “Machine Learning Guided Atom Mapping of Metabolic Reactions,” Journal of Chemical Information and Modeling, vol. 59, no. 3, pp. 1121–1135, Mar. 2019.
BibTeX
@article{litsa2019machine-learning-guided-atom, abstract = "Atom mapping of a chemical reaction is a mapping between the atoms in the reactant molecules and the atoms in the product molecules. It encodes the underlying reaction mechanism and, as such, constitutes essential information in computational studies in metabolic engineering. Various techniques have been investigated for the automatic computation of the atom mapping of a chemical reaction, approaching the problem as a graph matching problem. The graph abstraction of the chemical problem, though, eliminates crucial chemical information. There have been efforts for enhancing the graph representation by introducing the bond stabilities as edge weights, as they are estimated based on experimental evidence. Here, we present a fully automated optimization-based approach, named AMLGAM, (Automated Machine Learning Guided Atom Mapping), that uses machine learning techniques for the estimation of the bond stabilities based on the chemical environment of each bond. The optimization method finds the reaction mechanism which favors the breakage/formation of the less stable bonds. We evaluated our method on a manually curated data set of 382 chemical reactions and ran our method on a much larger and diverse data set of 7400 chemical reactions. We show that the proposed method improves the accuracy over existing techniques based on results published by earlier studies on a common data set and is capable of handling unbalanced reactions.", author = "Litsa, Eleni E. and Pe{\~n}a, Matthew I. and Moll, Mark and Giannakopoulos, George and Bennett, George N. and Kavraki, Lydia E.", doi = "10.1021/acs.jcim.8b00434", journal = "Journal of Chemical Information and Modeling", month = mar, number = "3", pages = "1121--1135", title = "Machine Learning Guided Atom Mapping of Metabolic Reactions", volume = "59", year = "2019" }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.
- J. D. Hernández, E. Vidal, M. Moll, N. Palomeras, M. Carreras, and L. E. Kavraki, “Online Motion Planning for Unexplored Underwater Environments using Autonomous Underwater Vehicles,” Journal of Field Robotics, vol. 36, no. 2, pp. 370–396, Mar. 2019.
BibTeX
@article{hernandez2019online-motion-planning-for-unexplored, abstract = "We present an approach to endow an autonomous underwater vehicle (AUV) with the capabilities to move through unexplored environments. To do so, we propose a computational framework for planning feasible and safe paths. The framework allows the vehicle to incrementally build a map of the surroundings, while simultaneously (re)planning a feasible path to a specified goal. To accomplish this, the framework considers motion constraints to plan feasible 3D paths, i.e., those that meet the vehicle's motion capabilities. It also incorporates a risk function to avoid navigating close to nearby obstacles. Furthermore, the framework makes use of two strategies to ensure meeting online computation limitations. The first one is to reuse the last best known solution to eliminate time-consuming pruning routines. The second one is to opportunistically check the states' risk of collision. To evaluate the proposed approach, we use the Sparus II performing autonomous missions in different real-world scenarios. These experiments consist of simulated and in-water trials for different tasks. The conducted tasks include the exploration of challenging scenarios such as artificial marine structures, natural marine structures, and confined natural environments. All these applications allow us to extensively prove the efficacy of the presented approach, not only for constant-depth missions (2D), but, more importantly, for situations in which the vehicle must vary its depth (3D).", author = "Hern{\'a}ndez, Juan David and Vidal, Eduard and Moll, Mark and Palomeras, N. and Carreras, Marc and Kavraki, Lydia E.", doi = "10.1002/rob.21827", journal = "Journal of Field Robotics", month = mar, number = "2", pages = "370--396", title = "Online Motion Planning for Unexplored Underwater Environments using Autonomous Underwater Vehicles", volume = "36", year = "2019" }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).
- W. C. Lewis II, M. Moll, and L. E. Kavraki, “How Much Do Unstated Problem Constraints Limit Deep Robotic Reinforcement Learning?,” Rice University, Department of Computer Science, Houston, Texas, TR19-01, 2019.
BibTeX
@techreport{lewis2019how-much-do-unstated-problem-constraints, 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.", address = "Houston, Texas", author = "Lewis~II, W. Cannon and Moll, Mark and Kavraki, Lydia E.", doi = "10.25611/az5z-xt37", institution = "Rice University, Department of Computer Science", number = "TR19-01", title = "How Much Do Unstated Problem Constraints Limit Deep Robotic Reinforcement Learning?", year = "2019" }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.
2018
- Z. Kingston, M. Moll, and L. E. Kavraki, “Sampling-Based Methods for Motion Planning with Constraints,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, pp. 159–185, May 2018.
BibTeX
@article{kingston2018sampling-based-methods-for-motion-planning, abstract = "Robots with many degrees of freedom (e.g., humanoid robots and mobile manipulators) have increasingly been employed to accomplish realistic tasks in domains such as disaster relief, spacecraft logistics, and home caretaking. Finding feasible motions for these robots autonomously is essential for their operation. Sampling-based motion planning algorithms have been shown to be effective for these high-dimensional systems. However, incorporating task constraints (e.g., keeping a cup level, writing on a board) into the planning process introduces significant challenges. is survey describes the families of methods for sampling-based planning with constraints and places them on a spectrum delineated by their complexity. Constrained sampling-based methods are based upon two core primitive operations: (1) sampling constraint-satisfying configurations and (2) generating constraint-satisfying continuous motion. Although the basics of sampling-based planning are presented for contextual background, the survey focuses on the representation of constraints and sampling- based planners that incorporate constraints.", author = "Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.", doi = "10.1146/annurev-control-060117-105226", journal = "Annual Review of Control, Robotics, and Autonomous Systems", keywords = "robotics, robot motion planning, sampling-based planning, constraints, planning with constraints, planning for high-dimensional robotic systems", month = may, pages = "159--185", title = "Sampling-Based Methods for Motion Planning with Constraints", volume = "1", year = "2018" }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.
- Muhayyuddin, M. Moll, L. E. Kavraki, and J. Rosell, “Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments,” IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 712–719, Apr. 2018.
BibTeX
@article{muhayyuddin2018randomized-physics-based-motion-planning, abstract = "Planning motions to grasp an object in cluttered and uncertain environments is a challenging task, particularly when a collision-free trajectory does not exist and objects obstructing the way are required to be carefully grasped and moved out. This paper takes a different approach and proposes to address this problem by using a randomized physics-based motion planner that permits robot-object and object-object interactions. The main idea is to avoid an explicit high-level reasoning of the task by providing the motion planner with a physics engine to evaluate possible complex multi-body dynamical interactions. The approach is able to solve the problem in complex scenarios, also considering uncertainty in the objects' pose and in the contact dynamics. The work enhances the state validity checker, the control sampler and the tree exploration strategy of a kinodynamic motion planner called KPIECE. The enhanced algorithm, called p-KPIECE, has been validated in simulation and with real experiments. The results have been compared with an ontological physics-based motion planner and with task and motion planning approaches, resulting in a significant improvement in terms of planning time, success rate and quality of the solution path.", author = "Muhayyuddin and Moll, Mark and Kavraki, Lydia E. and Rosell, Jan", doi = "10.1109/LRA.2017.2783445", journal = "IEEE Robotics and Automation Letters", keywords = "Physics-based motion planning, planning under uncertainties, clutter grasping", month = apr, number = "2", pages = "712--719", title = "Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments", volume = "3", year = "2018" }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 kinodynamic 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.
- D. Devaurs, M. Papanastasiou, D. Antunes, J. Abella, M. Moll, D. Ricklin, J. Lambris, and L. E. Kavraki, “Native State of Complement Protein C3d Analyzed via Hydrogen Exchange and Conformational Sampling,” Intl. J. of Computational Biology and Drug Design, vol. 11, no. 1/2, pp. 90–113, Mar. 2018. Special issue on the 2016 Intl. Conf. on Intelligent Biology and Medicine (ICIBM).
BibTeX
@article{devaurs2018native-state-of-complement-protein, 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.", author = "Devaurs, Didier and Papanastasiou, Malvina and Antunes, Dinler and Abella, Jayvee and Moll, Mark and Ricklin, Daniel and Lambris, John and Kavraki, Lydia E.", doi = "10.1504/IJCBDD.2018.10011903", journal = "Intl.\ J.\ of Computational Biology and Drug Design", keywords = "complement protein C3d; hydrogen exchange; mass spectrometry; protein conformational sampling; coarse-grained conformational sampling; native state; X-ray crystallography; molecular dynamics; protein structures; conformational ensembles", month = mar, note = "Special issue on the 2016 Intl.\ Conf.\ on Intelligent Biology and Medicine (ICIBM).", number = "1/2", pages = "90--113", title = "Native State of Complement Protein {C3d} Analyzed via Hydrogen Exchange and Conformational Sampling", volume = "11", year = "2018" }Abstract
Hydrogen/deuterium exchange detected by mass spectrometry (HDX-MS) provides valuable information on protein structure and dynamics. Although HDX-MS data is often interpreted using crystal structures, it was suggested that conformational ensembles produced by molecular dynamics simulations yield more accurate interpretations. In this paper, we analyse the complement protein C3d through HDX-MS data and evaluate several interpretation methodologies, using an existing prediction model to derive HDX-MS data from protein structure. We perform an HDX-MS experiment on C3d and, then, to interpret and refine the obtained data, we look for a conformation (or conformational ensemble) of C3d that allows computationally replicating this data. First, we confirm that crystal structures are not a good choice. Second, we suggest that conformational ensembles produced by molecular dynamics simulations might not always be satisfactory either. Finally, we show that coarse-grained conformational sampling of C3d produces a conformation from which the HDX-MS data can be replicated and refined.
- D. A. Antunes, D. Devaurs, M. Moll, G. Lizée, and L. E. Kavraki, “General Prediction of Peptide-MHC Binding Modes Using Incremental Docking: A Proof of Concept,” Scientific Reports, vol. 8, no. 1, p. 4327, Mar. 2018.
BibTeX
@article{antunes2018general-prediction-of-peptide-mhc-binding, 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.", author = "Antunes, Dinler A. and Devaurs, Didier and Moll, Mark and Liz{\'e}e, Gregory and Kavraki, Lydia E.", doi = "10.1038/s41598-018-22173-4", journal = "Scientific Reports", keywords = "Peptide-MHC, HLA, molecular docking, geometry prediction, cancer immunotherapy", month = mar, number = "1", pages = "4327", publisher = "Nature Publishing Group", title = "General Prediction of Peptide-{MHC} Binding Modes Using Incremental Docking: A Proof of Concept", volume = "8", year = "2018" }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.
- J. R. Abella, M. Moll, and L. E. Kavraki, “Maintaining and Enhancing Diversity of Sampled Protein Conformations in Robotics-Inspired Methods,” Journal of Computational Biology, vol. 25, no. 1, pp. 3–20, Jan. 2018.
BibTeX
@article{abella2018maintaining-and-enhancing-diversity-of-sampled, abstract = "The ability to efficiently sample structurally diverse protein conformations allows one to gain a high-level view of a protein's energy landscape. Algorithms from robot motion planning have been used for conformational sampling and promote diversity by keeping track of ``coverage'' in conformational space based on the local sampling density. However, large proteins present special challenges. In particular, larger systems require running many concurrent instances of these algorithms, but these algorithms can quickly become memory intensive because they typically keep previously sampled conformations in memory to maintain coverage estimates. Additionally, many of these algorithms depend on defining useful perturbation strategies for exploring the conformational space, which is a very difficult task for large proteins because such systems are typically more constrained and exhibit complex motions. In this paper, we introduce two methodologies for maintaining and enhancing diversity in robotics-inspired conformational sampling. The first method leverages the use of a low-dimensional projection to define a global coverage grid that maintains coverage across concurrent runs of sampling. The second method is an automatic definition of a perturbation strategy through readily available flexibility information derived from B-factors, secondary structure, and rigidity analysis. Our results show a significant increase in the diversity of the conformations sampled for proteins consisting of up to 500 residues. The methodologies presented in this paper may be vital components for the scalability of robotics-inspired approaches. ", author = "Abella, Jayvee R. and Moll, Mark and Kavraki, Lydia E.", doi = "10.1089/cmb.2017.0164", journal = "Journal of Computational Biology", keywords = "protein conformational sampling, robotics-inspired sampling, perturbation strategies, parallelization", month = jan, number = "1", pages = "3--20", title = "Maintaining and Enhancing Diversity of Sampled Protein Conformations in Robotics-Inspired Methods", volume = "25", year = "2018" }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.
2017
- D. A. Antunes, M. Moll, D. Devaurs, K. Jackson, G. Lizée, and L. E. Kavraki, “DINC 2.0: a new protein-peptide docking webserver using an incremental approach,” Cancer Research, vol. 77, no. 21, pp. e55–57, Nov. 2017.
BibTeX
@article{antunes2017dinc2, 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 for 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 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 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.", author = "Antunes, Dinler A. and Moll, Mark and Devaurs, Didier and Jackson, Kyle and Liz{\'e}e, Gregory and Kavraki, Lydia E.", doi = "10.1158/0008-5472.CAN-17-0511", journal = "Cancer Research", month = nov, number = "21", pages = "e55-57", title = "{DINC} 2.0: a new protein-peptide docking webserver using an incremental approach", volume = "77", year = "2017" }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 for 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 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 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.
- S. M. Kim, M. I. Peña, M. Moll, G. N. Bennett, and L. E. Kavraki, “A Review of Parameters and Heuristics for Guiding Metabolic Pathfinding,” Journal of Cheminformatics, vol. 9, no. 1, p. 51, Sep. 2017.
BibTeX
@article{kim2017a-review-of-parameters-and-heuristics-for-guiding, 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.", author = "Kim, Sarah M. and Pe{\~n}a, Matthew I. and Moll, Mark and Bennett, George N. and Kavraki, Lydia E.", doi = "10.1186/s13321-017-0239-6", journal = "Journal of Cheminformatics", keywords = "metabolic pathfinding; graph-based search; metabolic engineering", month = sep, number = "1", pages = "51", title = "A Review of Parameters and Heuristics for Guiding Metabolic Pathfinding", volume = "9", year = "2017" }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.
- W. Baker, Z. Kingston, M. Moll, J. Badger, and L. Kavraki, “Robonaut 2 and You: Specifying and Executing Complex Operations,” in IEEE Workshop on Advanced Robotics and its Social Impacts (ARSO), Austin, TX, 2017.
BibTeX
@inproceedings{baker2017robonaut-2-and-you, abstract = "Crew time is a precious resource due to the expense of trained human operators in space. Efficient caretaker robots could lessen the manual labor load required by frequent vehicular and life support maintenance tasks, freeing astronaut time for scientific mission objectives. Humanoid robots can fluidly exist alongside human counterparts due to their form, but they are complex and high-dimensional platforms. This paper describes a system that human operators can use to maneuver Robonaut 2 (R2), a dexterous humanoid robot developed by NASA to research co-robotic applications. The system includes a specification of constraints used to describe operations, and the supporting planning framework that solves constrained problems on R2 at interactive speeds. The paper is developed in reference to an illustrative, typical example of an operation R2 performs to highlight the challenges inherent to the problems R2 must face. Finally, the interface and planner is validated through a case-study using the guiding example on the physical robot in a simulated microgravity environment. This work reveals the complexity of employing humanoid caretaker robots and suggest solutions that are broadly applicable.", address = "Austin, TX", author = "Baker, William and Kingston, Zachary and Moll, Mark and Badger, Julia and Kavraki, Lydia", booktitle = "IEEE Workshop on Advanced Robotics and its Social Impacts (ARSO)", doi = "10.1109/ARSO.2017.8025204", month = mar, title = "Robonaut 2 and You: Specifying and Executing Complex Operations", year = "2017" }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.
- D. Devaurs, D. A. Antunes, M. Papanastasiou, M. Moll, D. Ricklin, J. D. Lambris, and L. E. Kavraki, “Coarse-Grained Conformational Sampling of Protein Structure Improves the Fit to Experimental Hydrogen-Exchange Data,” Frontiers in Molecular Biosciences, vol. 4, no. 13, Mar. 2017.
BibTeX
@article{devaurs2017coarse-grained-conformational-sampling-of-protein, 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 an accurate 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.", author = "Devaurs, Didier and Antunes, Dinler A and Papanastasiou, Malvina and Moll, Mark and Ricklin, Daniel and Lambris, John D and Kavraki, Lydia E", doi = "10.3389/fmolb.2017.00013", journal = "Frontiers in Molecular Biosciences", month = mar, number = "13", title = "Coarse-Grained Conformational Sampling of Protein Structure Improves the Fit to Experimental Hydrogen-Exchange Data", volume = "4", year = "2017" }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 an accurate 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.
- A. Novinskaya, D. Devaurs, M. Moll, and L. E. Kavraki, “Defining Low-Dimensional Projections to Guide Protein Conformational Sampling,” Journal of Computational Biology, vol. 24, no. 1, pp. 79–89, Jan. 2017.
BibTeX
@article{novinskaya2017defining-low-dimensional-projections-to-guide, 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 proteins. 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.", author = "Novinskaya, Anastasia and Devaurs, Didier and Moll, Mark and Kavraki, Lydia E.", doi = "10.1089/cmb.2016.0144", journal = "Journal of Computational Biology", keywords = "protein conformational sampling, protein flexibility, sampling- based planning, low-dimensional projection", month = jan, number = "1", pages = "79-89", title = "Defining Low-Dimensional Projections to Guide Protein Conformational Sampling", volume = "24", year = "2017" }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 proteins. 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.
2016
- J. D. Hernández, M. Moll, E. Vidal Garcia, M. Carreras, and L. E. Kavraki, “Planning Feasible and Safe Paths Online for Autonomous Underwater Vehicles in Unknown Environments,” in IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, 2016, pp. 1313–1320.
BibTeX
@inproceedings{hernandez2016planning-feasible-and-safe-paths, abstract = "We present a framework for planning collision-free and safe paths online for autonomous underwater vehicles (AUVs) in unknown environments. We build up on our previous work and propose an improved approach. While preserving its main modules (mapping, planning and mission handler), the framework now considers motion constraints to plan feasible paths, i.e., those that meet vehicle's motion capabilities. The new framework also incorporates a risk function to avoid navigating close to nearby obstacles, and reuses the last best known solution to eliminate time-consuming pruning routines. To evaluate this approach, we use the Sparus II AUV, a torpedo-shaped vehicle performing autonomous missions in a 2-dimensional workspace. We validate the framework's new features by solving tasks in both simulation and real-world in water trials and comparing results with our previous approach.", author = "Hern{\'a}ndez, Juan David and Moll, Mark and Vidal Garcia, Eduard and Carreras, Marc and Kavraki, Lydia E.", booktitle = "{IEEE/RSJ} Intl.\ Conf.\ on Intelligent Robots and Systems", doi = "10.1109/IROS.2016.7759217", month = oct, pages = "1313-1320", title = "Planning Feasible and Safe Paths Online for Autonomous Underwater Vehicles in Unknown Environments", year = "2016" }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.
- M. Moll, P. W. Finn, and L. E. Kavraki, “Structure-Guided Selection of Specificity Determining Positions in the Human Kinome,” BMC Genomics, vol. 17 (Suppl. 4), p. 431, Aug. 2016.
BibTeX
@article{moll2016structure-guided-selection-of-specificity-determining, abstract = "Background: The human kinome contains many important drug targets. It is well-known that inhibitors of protein kinases bind with very different selectivity profiles. This is also the case for inhibitors of many other protein families. The increased availability of protein 3D structures has provided much information on the structural variation within a given protein family. However, the relationship between structural variations and binding specificity is complex and incompletely understood. We have developed a structural bioinformatics approach which provides an analysis of key determinants of binding selectivity as a tool to enhance the rational design of drugs with a specific selectivity profile. Results: We propose a greedy algorithm that computes a subset of residue positions in a multiple sequence alignment such that structural and chemical variation in those positions helps explain known binding affinities. By providing this information, the main purpose of the algorithm is to provide experimentalists with possible insights into how the selectivity profile of certain inhibitors is achieved, which is useful for lead optimization. In addition, the algorithm can also be used to predict binding affinities for structures whose affinity for a given inhibitor is unknown. The algorithm's performance is demonstrated using an extensive dataset for the human kinome. Conclusion: We show that the binding affinity of 38 different kinase inhibitors can be explained with consistently high precision and accuracy using the variation of at most six residue positions in the kinome binding site. We show for several inhibitors that we are able to identify residues that are known to be functionally important.", author = "Moll, Mark and Finn, Paul W. and Kavraki, Lydia E.", doi = "10.1186/s12864-016-2790-3", journal = "BMC Genomics", keywords = "protein kinases; specificity determining positions; binding affinity", month = aug, pages = "431", title = "Structure-Guided Selection of Specificity Determining Positions in the Human Kinome", volume = "17 (Suppl.\ 4)", year = "2016" }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.
- S. M. Kim, M. I. Peña, M. Moll, G. Giannakopoulos, G. N. Bennett, and L. E. Kavraki, “An Evaluation of Different Clustering Methods and Distance Measures Used for Grouping Metabolic Pathways,” in Eighth International Conference on Bioinformatics and Computational Biology (BICoB), 2016.
BibTeX
@inproceedings{kim2016an-evaluation-of-different-clustering-methods, abstract = "Large-scale annotated metabolic databases, such as KEGG and MetaCyc, provide a wealth of information to researchers designing novel biosynthetic pathways. However, many metabolic pathfinding tools that assist in identifying possible solution pathways fail to facilitate the grouping and interpretation of these pathway results. Clustering possible solution pathways can help users of pathfinding tools quickly notice 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, showing that clustering methods may not be capable of grouping pathways with more complex underlying topographies.", 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 = "Eighth International Conference on Bioinformatics and Computational Biology (BICoB)", month = apr, title = "An Evaluation of Different Clustering Methods and Distance Measures Used for Grouping Metabolic Pathways", year = "2016" }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 notice 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, showing that clustering methods may not be capable of grouping pathways with more complex underlying topographies.
- L. E. Kavraki and M. Moll, “Special Issue on the 2014 ‘Robotics: Science & Systems,’ Intl. J. of Robotics Research, vol. 35, no. 1–3, pp. 3–4, Mar. 2016.
BibTeX
@article{kavraki2016rss2014, author = "Kavraki, Lydia E. and Moll, Mark", doi = "10.1177/0278364915608299", journal = "Intl.\ J.\ of Robotics Research", month = mar, number = "1--3", pages = "3--4", title = "Special Issue on the 2014 ``{R}obotics: {S}cience \& {S}ystems'' Conference (Guest Editorial)", volume = "35", year = "2016" }
2015
- A. Novinskaya, D. Devaurs, M. Moll, and L. E. Kavraki, “Improving Protein Conformational Sampling by Using Guiding Projections,” in IEEE Intl. Conf. on Bioinformatics and Biomedicine Workshops (BIBMW), 2015, pp. 1272–1279.
BibTeX
@inproceedings{novinskaya2015improving-protein-conformational-sampling, 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.", author = "Novinskaya, Anastasia and Devaurs, Didier and Moll, Mark and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Bioinformatics and Biomedicine Workshops (BIBMW)", doi = "10.1109/BIBM.2015.7359863", month = nov, pages = "1272-1279", title = "Improving Protein Conformational Sampling by Using Guiding Projections", year = "2015" }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.
- M. Moll, P. W. Finn, and L. E. Kavraki, “Structure-Guided Selection of Specificity Determining Positions in the Human Kinome,” in IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2015, pp. 21–28.
BibTeX
@inproceedings{moll2015structure-guided-selection-of-specificity-determining, abstract = "It is well-known that inhibitors of protein kinases bind with very different selectivity profiles. This is also the case for inhibitors of many other protein families. A better understanding of binding selectivity would enhance the design of drugs that target only a subfamily, thereby minimizing possible side-effects. The increased availability of protein 3D structures has made it possible to study the structural variation within a given protein family. However, not every structural variation is related to binding specificity. We propose a greedy algorithm that computes a subset of residue positions in a multiple sequence alignment such that structural and chemical variation in those positions helps explain known binding affinities. By providing this information, the main purpose of the algorithm is to provide experimentalists with possible insights into how the selectivity profile of certain inhibitors is achieved, which is useful for lead optimization. In addition, the algorithm can also be used to predict binding affinities for structures whose affinity for a given inhibitor is unknown. The algorithm's performance is demonstrated using an extensive dataset for the human kinome, which includes a large and important set of drug targets. We show that the binding affinity of 38 different kinase inhibitors can be explained with consistently high precision and accuracy using the variation of at most six residue positions in the kinome binding site. ", author = "Moll, Mark and Finn, Paul W. and Kavraki, Lydia E.", booktitle = "IEEE International Conference on Bioinformatics and Biomedicine (BIBM)", doi = "10.1109/BIBM.2015.7359650", month = nov, pages = "21--28", title = "Structure-Guided Selection of Specificity Determining Positions in the Human Kinome", year = "2015" }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.
- M. Moll, I. A. Şucan, and L. E. Kavraki, “Benchmarking Motion Planning Algorithms: An Extensible Infrastructure for Analysis and Visualization,” IEEE Robotics & Automation Magazine (Special Issue on Replicable and Measurable Robotics Research), vol. 22, no. 3, pp. 96–102, Sep. 2015.
BibTeX
@article{moll2015benchmarking-motion-planning-algorithms, 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.", author = "Moll, Mark and {\c{S}}ucan, Ioan A. and Kavraki, Lydia E.", doi = "10.1109/MRA.2015.2448276", journal = "{IEEE} Robotics \& Automation Magazine (Special Issue on Replicable and Measurable Robotics Research)", month = sep, number = "3", pages = "96--102", title = "Benchmarking Motion Planning Algorithms: An Extensible Infrastructure for Analysis and Visualization", volume = "22", year = "2015" }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.
- D. K. Grady, M. Moll, and L. E. Kavraki, “Extending the Applicability of POMDP Solutions to Robotic Tasks,” IEEE Trans. on Robotics, vol. 31, no. 4, pp. 948–961, Aug. 2015.
BibTeX
@article{grady2015extending-the-applicability-of-pomdp-solutions, 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.", author = "Grady, Devin K. and Moll, Mark and Kavraki, Lydia E.", doi = "10.1109/TRO.2015.2441511", journal = "{IEEE} Trans.\ on Robotics", month = aug, number = "4", pages = "948--961", title = "Extending the Applicability of {POMDP} Solutions to Robotic Tasks", volume = "31", year = "2015" }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.
- D. Coleman, I. A. Şucan, M. Moll, K. Okada, and N. Correll, “Experience-Based Planning with Sparse Roadmap Spanners,” in IEEE Intl. Conf. on Robotics and Automation, 2015, pp. 900–905.
BibTeX
@inproceedings{coleman2015experience-based-planning-with-sparse, abstract = "We present an experienced-based planning framework called Thunder that learns to reduce computation time required to solve high-dimensional planning problems in varying environments. The approach is especially suited for large configuration spaces that include many invariant constraints, such as those found with whole body humanoid motion planning. Experiences are generated using probabilistic sampling and stored in a sparse roadmap spanner (SPARS), which provides asymptotically near-optimal coverage of the configuration space, making storing, retrieving, and repairing past experiences very efficient with respect to memory and time. The Thunder framework improves upon past experience- based planners by storing experiences in a graph rather than in individual paths, eliminating redundant information, providing more opportunities for path reuse, and providing a theoretical limit to the size of the experience graph. These properties also lead to improved handling of dynamically changing environments, reasoning about optimal paths, and reducing query resolution time. The approach is demonstrated on a 30 degrees of freedom humanoid robot and compared with the Lightning framework, an experience-based planner that uses individual paths to store past experiences. In environments with variable obstacles and stability constraints, experiments show that Thunder is on average an order of magnitude faster than Lightning and planning from scratch. Thunder also uses 98.8% less memory to store its experiences after 10,000 trials when compared to Lightning. Our framework is implemented and freely available in the Open Motion Planning Library.", author = "Coleman, David and {\c{S}}ucan, Ioan A. and Moll, Mark and Okada, Kei and Correll, Nikolaus", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2015.7139284", month = may, pages = "900--905", title = "Experience-Based Planning with Sparse Roadmap Spanners", year = "2015" }Abstract
We present an experienced-based planning framework called Thunder that learns to reduce computation time required to solve high-dimensional planning problems in varying environments. The approach is especially suited for large configuration spaces that include many invariant constraints, such as those found with whole body humanoid motion planning. Experiences are generated using probabilistic sampling and stored in a sparse roadmap spanner (SPARS), which provides asymptotically near-optimal coverage of the configuration space, making storing, retrieving, and repairing past experiences very efficient with respect to memory and time. The Thunder framework improves upon past experience- based planners by storing experiences in a graph rather than in individual paths, eliminating redundant information, providing more opportunities for path reuse, and providing a theoretical limit to the size of the experience graph. These properties also lead to improved handling of dynamically changing environments, reasoning about optimal paths, and reducing query resolution time. The approach is demonstrated on a 30 degrees of freedom humanoid robot and compared with the Lightning framework, an experience-based planner that uses individual paths to store past experiences. In environments with variable obstacles and stability constraints, experiments show that Thunder is on average an order of magnitude faster than Lightning and planning from scratch. Thunder also uses 98.8% less memory to store its experiences after 10,000 trials when compared to Lightning. Our framework is implemented and freely available in the Open Motion Planning Library.
- C. Voss, M. Moll, and L. E. Kavraki, “A Heuristic Approach to Finding Diverse Short Paths,” in IEEE Intl. Conf. on Robotics and Automation, 2015, pp. 4173–4179.
BibTeX
@inproceedings{voss2015a-heuristic-approach-to-finding-diverse, 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'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.", author = "Voss, Caleb and Moll, Mark and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2015.7139774", month = may, pages = "4173--4179", title = "A Heuristic Approach to Finding Diverse Short Paths", year = "2015" }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’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.
- R. Luna, M. Lahijanian, M. Moll, and L. E. Kavraki, “Asymptotically Optimal Stochastic Motion Planning with Temporal Goals,” in Algorithmic Foundations of Robotics XI, vol. 107, H. L. Akin, N. M. Amato, V. Isler, and A. F. van der Stappen, Eds. Springer Verlag, 2015, pp. 335–352.
BibTeX
@incollection{luna2015asymptotically-optimal-stochastic-motion, 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. ", author = "Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E.", booktitle = "Algorithmic Foundations of Robotics XI", doi = "10.1007/978-3-319-16595-0_20", editor = "Akin, H. Levent and Amato, Nancy M. and Isler, Volkan and van der Stappen, A. Frank", keywords = "planning under uncertainty, temporal logic planning, stochastic systems, formal control synthesis", pages = "335--352", publisher = "Springer Verlag", series = "Springer Tracts in Advanced Robotics", title = "Asymptotically Optimal Stochastic Motion Planning with Temporal Goals", volume = "107", year = "2015" }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.
2014
- R. Luna, M. Lahijanian, M. Moll, and L. E. Kavraki, “Optimal and Efficient Stochastic Motion Planning in Partially-Known Environments,” in 28th AAAI Conference on Artificial Intelligence (AAAI-14), Québec City, Canada, 2014, pp. 2549–2555.
BibTeX
@inproceedings{luna2014optimal-and-efficient-stochastic-motion, 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 = "Qu\'ebec City, Canada", author = "Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E.", booktitle = "28th AAAI Conference on Artificial Intelligence (AAAI-14)", month = jul, pages = "2549--2555", title = "Optimal and Efficient Stochastic Motion Planning in Partially-Known Environments", url = "https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8457", year = "2014" }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.
- Z. Wang, Z. Wang, M. Moll, P.-S. Huang, D. Grady, N. Nasrabadi, T. Huang, L. Kavraki, and M. Hasegawa-Johnson, “Active Planning, Sensing and Recognition Using a Resource-Constrained Discriminant POMDP,” in IEEE/ISPRS Workshop on Multi-Sensor Fusion for Outdoor Dynamic Scene Understanding at CVPR, 2014.
BibTeX
@inproceedings{wang2014active-planning-sensing-and-recognition, 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 -- such as motion, number of measurements and bandwidth -- 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.", author = "Wang, Zhaowen and Wang, Zhangyang and Moll, Mark and Huang, Po-Sen and Grady, Devin and Nasrabadi, Nasser and Huang, Thomas and Kavraki, Lydia and Hasegawa-Johnson, Mark", booktitle = "IEEE/ISPRS Workshop on Multi-Sensor Fusion for Outdoor Dynamic Scene Understanding at CVPR", doi = "10.1109/CVPRW.2014.116", month = jun, title = "Active Planning, Sensing and Recognition Using a Resource-Constrained Discriminant {POMDP}", year = "2014" }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 – such as motion, number of measurements and bandwidth – 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.
- S. Nedunuri, S. Prabhu, M. Moll, S. Chaudhuri, and L. E. Kavraki, “SMT-Based Synthesis of Integrated Task and Motion Plans from Plan Outlines,” in IEEE Intl. Conf. on Robotics and Automation, 2014, pp. 655–662.
BibTeX
@inproceedings{nedunuri2014smt-based-synthesis-of-integrated-task, abstract = "We present a new approach to integrated task and motion planning (ITMP) for robots performing mobile manipulation. In our approach, the user writes a high-level specification that captures partial knowledge about a mobile manipulation setting. In particular, this specification includes a plan outline that syntactically defines a space of plausible integrated plans, a set of logical requirements that the generated plan must satisfy, and a description of the physical space that the robot manipulates. A synthesis algorithm is now used to search for an integrated plan that falls within the space defined by the plan outline, and also satisfies all requirements. Our synthesis algorithm complements continuous motion planning algorithms with calls to a Satisfiability Modulo Theories (SMT) solver. From the scene description, a motion planning algorithm is used to construct a placement graph, an abstraction of a manipulation 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. Our approach is implemented in a system called ROBOSYNTH. We have evaluated ROBOSYNTH on a generalization of an ITMP problem investigated in prior work. The experiments demonstrate that our method is capable of generating integrated plans for a number of interesting variations on the problem.", author = "Nedunuri, Srinivas and Prabhu, Sailesh and Moll, Mark and Chaudhuri, Swarat and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2014.6906924", month = may, pages = "655-662", title = "{SMT}-Based Synthesis of Integrated Task and Motion Plans from Plan Outlines", year = "2014" }Abstract
We present a new approach to integrated task and motion planning (ITMP) for robots performing mobile manipulation. In our approach, the user writes a high-level specification that captures partial knowledge about a mobile manipulation setting. In particular, this specification includes a plan outline that syntactically defines a space of plausible integrated plans, a set of logical requirements that the generated plan must satisfy, and a description of the physical space that the robot manipulates. A synthesis algorithm is now used to search for an integrated plan that falls within the space defined by the plan outline, and also satisfies all requirements. Our synthesis algorithm complements continuous motion planning algorithms with calls to a Satisfiability Modulo Theories (SMT) solver. From the scene description, a motion planning algorithm is used to construct a placement graph, an abstraction of a manipulation 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. Our approach is implemented in a system called ROBOSYNTH. We have evaluated ROBOSYNTH on a generalization of an ITMP problem investigated in prior work. The experiments demonstrate that our method is capable of generating integrated plans for a number of interesting variations on the problem.
- R. Luna, M. Lahijanian, M. Moll, and L. E. Kavraki, “Fast Stochastic Motion Planning with Optimality Guarantees using Local Policy Reconfiguration,” in IEEE Intl. Conf. on Robotics and Automation, 2014, pp. 3013–3019.
BibTeX
@inproceedings{luna2014fast-stochastic-motion-planning, 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.", author = "Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2014.6907293", pages = "3013-3019", title = "Fast Stochastic Motion Planning with Optimality Guarantees using Local Policy Reconfiguration", year = "2014" }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.
2013
- D. K. Grady, M. Moll, and L. E. Kavraki, “Combining a POMDP Abstraction with Replanning to Solve Complex, Position-Dependent Sensing Tasks,” in AAAI Fall Symposium, Arlington, VA, 2013.
BibTeX
@inproceedings{grady2013combining-a-pomdp-abstraction-with-replanning, abstract = "The Partially-Observable Markov Decision Process (POMDP) is a general framework to determine reward-maximizing action policies under noisy action and sensing. 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 pro- vide 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 -- 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. It is empirically demonstrated 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, VA", author = "Grady, Devin K. and Moll, Mark and Kavraki, Lydia E.", booktitle = "AAAI Fall Symposium", month = nov, title = "Combining a {POMDP} Abstraction with Replanning to Solve Complex, Position-Dependent Sensing Tasks", url = "https://www.aaai.org/ocs/index.php/FSS/FSS13/paper/view/7578", 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. 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 pro- vide 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 – 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. It is empirically demonstrated 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.
- J. Chyan, M. Moll, and L. E. Kavraki, “Improving the Prediction of Kinase Binding Affinity Using Homology Models,” in Computational Structural Bioinformatics Workshop at the ACM Conf. on Bioinf., Comp. Bio. and Biomedical Informatics, Washington, DC, 2013, pp. 741–748.
BibTeX
@inproceedings{chyan2013improving-the-prediction-of-kinase-binding, 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", author = "Chyan, Jeffrey and Moll, Mark and Kavraki, Lydia E.", booktitle = "Computational Structural Bioinformatics Workshop at the ACM Conf.\ on Bioinf., Comp.\ Bio.\ and Biomedical Informatics", doi = "10.1145/2506583.2506704", month = sep, pages = "741-748", title = "Improving the Prediction of Kinase Binding Affinity Using Homology Models", year = "2013" }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.
- B. Gipson, M. Moll, and L. E. Kavraki, “SIMS: A hybrid method for rapid conformational analysis,” PLOS ONE, vol. 8, no. 7, p. e68826, Jul. 2013.
BibTeX
@article{gipson2013sims-a-hybrid-method-for-rapid, 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.", author = "Gipson, Bryant and Moll, Mark and Kavraki, Lydia E.", doi = "10.1371/journal.pone.0068826", journal = "PLOS ONE", month = jul, number = "7", pages = "e68826", title = "{SIMS}: A hybrid method for rapid conformational analysis", volume = "8", year = "2013" }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.
- D. H. Bryant, M. Moll, P. W. Finn, and L. E. Kavraki, “Combinatorial clustering of residue position subsets predicts inhibitor affinity across the human kinome,” PLOS Computational Biology, vol. 9, no. 6, p. e1003087, Jun. 2013.
BibTeX
@article{bryant2013combinatorial-clustering-of-residue-position, 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.", author = "Bryant, Drew H. and Moll, Mark and Finn, Paul W. and Kavraki, Lydia E.", doi = "10.1371/journal.pcbi.1003087", journal = "PLOS Computational Biology", keywords = "kinases, binding affinity", month = jun, number = "6", pages = "e1003087", title = "Combinatorial clustering of residue position subsets predicts inhibitor affinity across the human kinome", volume = "9", year = "2013" }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.
- R. Luna, I. A. Şucan, M. Moll, and L. E. Kavraki, “Anytime Solution Optimization for Sampling-Based Motion Planning,” in IEEE Intl. Conf. on Robotics and Automation, 2013, pp. 5053–5059.
BibTeX
@inproceedings{luna2013anytime-solution-optimization, 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.", author = "Luna, Ryan and {\c{S}}ucan, Ioan A. and Moll, Mark and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2013.6631301", pages = "5053--5059", title = "Anytime Solution Optimization for Sampling-Based Motion Planning", year = "2013" }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.
- M. Moll, J. Bordeaux, and L. E. Kavraki, “Software for Project-Based Learning of Robot Motion Planning,” Computer Science Education, Special Issue on Robotics in CS Education, vol. 23, no. 4, pp. 332–348, 2013.
BibTeX
@article{moll2013software-for-project-based-learning-of-robot, 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.", author = "Moll, Mark and Bordeaux, Janice and Kavraki, Lydia E.", doi = "10.1080/08993408.2013.847167", journal = "Computer Science Education, Special Issue on Robotics in CS Education", keywords = "robotics education; motion planning; project-based learning; educational software", number = "4", pages = "332--348", title = "Software for Project-Based Learning of Robot Motion Planning", volume = "23", year = "2013" }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.
- D. K. Grady, M. Moll, and L. E. Kavraki, “Automated Model Approximation for Robotic Navigation with POMDPs,” in IEEE Intl. Conf. on Robotics and Automation, 2013, pp. 78–84.
BibTeX
@inproceedings{grady2013automated-model-approximation, 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.", author = "Grady, Devin K. and Moll, Mark and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2013.6630559", pages = "78--84", title = "Automated Model Approximation for Robotic Navigation with {POMDP}s", year = "2013" }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.
- B. Gipson, M. Moll, and L. E. Kavraki, “Resolution Independent Density Estimation for Motion Planning in High-Dimensional Spaces,” in IEEE Intl. Conf. on Robotics and Automation, 2013, pp. 2429–2435.
BibTeX
@inproceedings{gipson2013resolution-independent-density-estimation, 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.", author = "Gipson, Bryant and Moll, Mark and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ICRA.2013.6630908", pages = "2429--2435", title = "Resolution Independent Density Estimation for Motion Planning in High-Dimensional Spaces", year = "2013" }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.
2012
- I. A. Şucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,” IEEE Robotics & Automation Magazine, vol. 19, no. 4, pp. 72–82, Dec. 2012. http://ompl.kavrakilab.org
BibTeX
@article{sucan2012the-open-motion-planning-library, 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).", author = "{\c{S}}ucan, Ioan A. and Moll, Mark and Kavraki, Lydia E.", doi = "10.1109/MRA.2012.2205651", journal = "{IEEE} Robotics \& Automation Magazine", month = dec, note = "\url{http://ompl.kavrakilab.org}", number = "4", pages = "72--82", title = "The {O}pen {M}otion {P}lanning {L}ibrary", volume = "19", year = "2012" }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).
- K. E. Bekris, D. K. Grady, M. Moll, and L. E. Kavraki, “Safe Distributed Motion Coordination for Second-Order Systems with Different Planning Cycles,” Intl. J. of Robotics Research, vol. 31, no. 2, pp. 129–149, Feb. 2012.
BibTeX
@article{bekris2012safe-distributed-motion-coordination, abstract = "When multiple robots operate in the same environment, it is critical to coordinate their motion in a distributed fashion so that they reach their goals safely. If the robots have to respect second-order dynamics, this becomes a challenging problem, even for known static environments. This work presents a replanning framework where each robot computes partial plans independently during a planning 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 planning cycles over time. This paper proves that the proposed motion coordination algorithm guarantees safety under this general setting. An important advantage is that this framework is not specific to the underlying robot dynamics 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.", author = "Bekris, Kostas E. and Grady, Devin K. and Moll, Mark and Kavraki, Lydia E.", doi = "10.1177/0278364911430420", journal = "Intl.\ J.\ of Robotics Research", month = feb, number = "2", pages = "129--149", title = "Safe Distributed Motion Coordination for Second-Order Systems with Different Planning Cycles", volume = "31", year = "2012" }Abstract
When multiple robots operate in the same environment, it is critical to coordinate their motion in a distributed fashion so that they reach their goals safely. If the robots have to respect second-order dynamics, this becomes a challenging problem, even for known static environments. This work presents a replanning framework where each robot computes partial plans independently during a planning 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 planning cycles over time. This paper proves that the proposed motion coordination algorithm guarantees safety under this general setting. An important advantage is that this framework is not specific to the underlying robot dynamics 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.
- D. K. Grady, M. Moll, C. Hegde, A. C. Sankaranarayanan, R. G. Baraniuk, and L. E. Kavraki, “Multi-Objective Sensor-Based Replanning for a Car-Like Robot,” in IEEE Intl. Symp. on Safety, Security, and Rescue Robotics, 2012.
BibTeX
@inproceedings{grady2012multi-objective-sensor-based-replanning-for-a-car-like, 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' 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' 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.", author = "Grady, Devin K. and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E.", booktitle = "IEEE Intl.\ Symp.\ on Safety, Security, and Rescue Robotics", doi = "10.1109/SSRR.2012.6523898", title = "Multi-Objective Sensor-Based Replanning for a Car-Like Robot", year = "2012" }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’ 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’ 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.
- D. K. Grady, M. Moll, C. Hegde, A. C. Sankaranarayanan, R. G. Baraniuk, and L. E. Kavraki, “Multi-Robot Target Verification with Reachability Constraints,” in IEEE Intl. Symp. on Safety, Security, and Rescue Robotics, 2012.
BibTeX
@inproceedings{grady2012multi-robot-target-verification, 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.", author = "Grady, Devin K. and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E.", booktitle = "IEEE Intl.\ Symp.\ on Safety, Security, and Rescue Robotics", doi = "10.1109/SSRR.2012.6523873", title = "Multi-Robot Target Verification with Reachability Constraints", year = "2012" }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.
2011
- M. Moll, D. H. Bryant, and L. E. Kavraki, “The LabelHash Server and Tools for Substructure-Based Functional Annotation,” Bioinformatics, vol. 27, no. 15, pp. 2161–2162, Jun. 2011.
BibTeX
@article{moll2011the-labelhash-server-and-tools-for-substructure-based, 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. Contact: mmoll@rice.edu", author = "Moll, Mark and Bryant, Drew H. and Kavraki, Lydia E.", doi = "10.1093/bioinformatics/btr343", journal = "Bioinformatics", month = jun, number = "15", pages = "2161--2162", pmid = "21659320", title = "The {LabelHash} Server and Tools for Substructure-Based Functional Annotation", volume = "27", year = "2011" }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. Contact: mmoll@rice.edu
- M. Moll, I. A. Şucan, J. Bordeaux, and L. E. Kavraki, “Teaching Motion Planning Concepts to Undergraduate Students,” in IEEE Workshop on Advanced Robotics and its Social Impacts (ARSO), 2011.
BibTeX
@inproceedings{moll2011teaching-motion-planning-concepts, 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.", author = "Moll, Mark and {\c{S}}ucan, Ioan A. and Bordeaux, Janice and Kavraki, Lydia E.", booktitle = "IEEE Workshop on Advanced Robotics and its Social Impacts (ARSO)", doi = "10.1109/ARSO.2011.6301976", title = "Teaching Motion Planning Concepts to Undergraduate Students", year = "2011" }Abstract
Motion planning is a central problem in robotics. Although it is an engaging topic for undergraduate students, it is difficult to teach, and as a result, the material is often only covered at an abstract level. Deep learning could be achieved by having students implement and test different algorithms. However, there is usually no time within a single class to have students completely implement several motion planning algorithms as they require the development of many lower-level data structures. We present an ongoing project to develop a teaching module for robotic motion planning centered around an integrated software environment. The module can be taught early in the undergraduate curriculum, after students have taken an introductory programming class.
- D. K. Grady, M. Moll, C. Hegde, A. C. Sankaranarayanan, R. G. Baraniuk, and L. E. Kavraki, “Look Before You Leap: Predictive Sensing and Opportunistic Navigation,” in Workshop on Progress and Open Problems in Motion Planning at the IEEE/RSJ Conf. on Intelligent Robots and Systems, 2011.
BibTeX
@inproceedings{grady2011look-before-you-leap, 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 ``good'' 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' 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'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.", 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} Conf.\ on Intelligent Robots and Systems", title = "Look Before You Leap: Predictive Sensing and Opportunistic Navigation", 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 “good” 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’ 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’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.
2010
- M. Moll, D. H. Bryant, and L. E. Kavraki, “The LabelHash Algorithm for Substructure Matching,” BMC Bioinformatics, vol. 11, no. 555, Nov. 2010.
BibTeX
@article{moll2010the-labelhash-algorithm-for-substructure-matching, 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.", author = "Moll, Mark and Bryant, Drew H. and Kavraki, Lydia E.", doi = "10.1186/1471-2105-11-555", journal = "BMC Bioinformatics", month = nov, number = "555", pmcid = "PMC2996407", pmid = "21070651", title = "The {LabelHash} Algorithm for Substructure Matching", volume = "11", year = "2010" }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.
- D. H. Bryant, M. Moll, B. Y. Chen, V. Y. Fofanov, and L. E. Kavraki, “Analysis of substructural variation in families of enzymatic proteins with applications to protein function prediction,” BMC Bioinformatics, vol. 11, no. 242, May 2010.
BibTeX
@article{bryant2010analysis-of-substructural-variation-in-families, 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. ", author = "Bryant, Drew H. and Moll, Mark and Chen, Brian Y. and Fofanov, Viacheslav Y. and Kavraki, Lydia E.", doi = "10.1186/1471-2105-11-242", journal = "BMC Bioinformatics", month = may, number = "242", pmcid = "PMC2885373", pmid = "20459833", title = "Analysis of substructural variation in families of enzymatic proteins with applications to protein function prediction", volume = "11", year = "2010" }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.
- M. Moll, J. Bordeaux, and L. E. Kavraki, “Teaching Robot Motion Planning,” ASEE Computers in Education Journal (Special Issue on Novel Approaches to Robotics Education), vol. 20, no. 3, pp. 50–59, 2010.
BibTeX
@article{moll2010teaching-robot-motion-planning, 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.", author = "Moll, Mark and Bordeaux, Janice and Kavraki, Lydia E.", journal = "ASEE Computers in Education Journal (Special Issue on Novel Approaches to Robotics Education)", number = "3", pages = "50--59", title = "Teaching Robot Motion Planning", url = "https://www.asee.org/papers-and-publications/publications/division-publications/computers-in-education-journal/volume-xx", volume = "20", year = "2010" }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.
- N. Haspel, M. Moll, M. L. Baker, W. Chiu, and L. E. Kavraki, “Tracing Conformational Changes in Proteins,” BMC Structural Biology, vol. 10, no. Suppl. 1, p. S1, 2010.
BibTeX
@article{haspel2010tracing-conformational-changes-in-proteins, 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.", author = "Haspel, Nurit and Moll, Mark and Baker, Matthew L. and Chiu, Wah and Kavraki, Lydia E.", doi = "10.1186/1472-6807-10-S1-S1", journal = "BMC Structural Biology", number = "Suppl. 1", pages = "S1", pmcid = "PMC2873824", pmid = "20487508", title = "Tracing Conformational Changes in Proteins", volume = "10", year = "2010" }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.
2009
- N. Haspel, M. Moll, M. L. Baker, W. Chiu, and L. E. Kavraki, “Tracing Conformational Changes in Proteins,” in IEEE Intl. Conf. on Bioinformatics and Biomedicine Workshops (BIBMW), Washington, DC, 2009, pp. 120–127.
BibTeX
@inproceedings{haspel2009tracing-conformational-changes-in-proteins, 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 require 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", author = "Haspel, Nurit and Moll, Mark and Baker, Matthew L. and Chiu, Wah and Kavraki, Lydia E.", booktitle = "{IEEE} Intl.\ Conf.\ on Bioinformatics and Biomedicine Workshops (BIBMW)", doi = "10.1109/BIBMW.2009.5332115", month = nov, pages = "120--127", title = "Tracing Conformational Changes in Proteins", year = "2009" }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 require 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.
2008
- M. Moll and D. Rus, “Special Issue on Self-Reconfiguring Modular Robots (Guest Editorial),” Intl. J. of Robotics Research, vol. 27, no. 3/4, pp. 277–278, Mar. 2008.
BibTeX
@article{moll2008workshop-on-self-reconfigurable-modular-robots, author = "Moll, Mark and Rus, Daniela", doi = "10.1177/0278364908089348", journal = "Intl.\ J.\ of Robotics Research", month = mar, number = "3/4", pages = "277-278", title = "Special Issue on Self-Reconfiguring Modular Robots (Guest Editorial)", volume = "27", year = "2008" } - M. Moll and L. E. Kavraki, “LabelHash: A Flexible and Extensible Method for Matching Structural Motifs,” in Automated Function Prediction / BioSapiens Meeting (AFP-BioSapiens), Toronto, Canada, 2008. Available from Nature Precedings
BibTeX
@inproceedings{moll2008labelhash-a-flexible-and-extensible-method, address = "Toronto, Canada", author = "Moll, Mark and Kavraki, Lydia E.", booktitle = "Automated Function Prediction / BioSapiens Meeting (AFP-BioSapiens)", doi = "10.1038/npre.2008.2199.1", note = "Available from Nature Precedings", title = "{LabelHash}: A Flexible and Extensible Method for Matching Structural Motifs", year = "2008" } - M. Moll and L. E. Kavraki, “Matching of Structural Motifs Using Hashing on Residue Labels and Geometric Filtering for Protein Function Prediction,” in The Seventh Annual International Conference on Computational Systems Bioinformatics (CSB2008), 2008, pp. 157–168.
BibTeX
@inproceedings{moll2008matching-of-structural-motifs, 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/.", author = "Moll, Mark and Kavraki, Lydia E.", booktitle = "The Seventh Annual International Conference on Computational Systems Bioinformatics (CSB2008)", doi = "10.1142/9781848162648_0014", pages = "157-168", pmid = "19642277", title = "Matching of Structural Motifs Using Hashing on Residue Labels and Geometric Filtering for Protein Function Prediction", url = "http://csb2008.org/csb2008papers/077Moll.pdf", year = "2008" }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/.
- V. Y. Fofanov, B. Y. Chen, D. H. Bryant, M. Moll, O. Lichtarge, L. E. Kavraki, and M. Kimmel, “A statistical model to correct systematic bias introduced by algorithmic thresholds in protein structural comparison algorithms,” in IEEE Intl. Conf. on Bioinformatics and Biomedicine Workshops (BIBMW), 2008, pp. 1–8.
BibTeX
@inproceedings{fofanov2008a-statistical-model-to-correct-systematic, 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. ", author = "Fofanov, Viacheslav Y. and Chen, Brian Y. and Bryant, Drew H. and Moll, Mark and Lichtarge, Olivier and Kavraki, Lydia E. and Kimmel, Marek", booktitle = "{IEEE} Intl.\ Conf.\ on Bioinformatics and Biomedicine Workshops (BIBMW)", doi = "10.1109/BIBMW.2008.4686202", pages = "1--8", title = "A statistical model to correct systematic bias introduced by algorithmic thresholds in protein structural comparison algorithms", year = "2008" }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.
2007
- M. Moll, D. Schwarz, and L. E. Kavraki, “Roadmap Methods for Protein Folding,” in Protein Structure Prediction: Methods and Protocols, Second., M. Zaki and C. Bystroff, Eds. Humana Press, 2007.
BibTeX
@incollection{moll2007roadmap-methods-for-protein-folding, 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. ", author = "Moll, Mark and Schwarz, David and Kavraki, Lydia E.", booktitle = "Protein Structure Prediction: Methods and Protocols", doi = "10.1007/978-1-59745-574-9_9", edition = "Second", editor = "Zaki, Mohammed and Bystroff, Chris", month = oct, pmid = "18075168", publisher = "Humana Press", series = "Methods In Molecular Biology", title = "Roadmap Methods for Protein Folding", year = "2007" }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.
- M. Yim, W.-M. Shen, B. Salemi, D. Rus, M. Moll, H. Lipson, and E. Klavins, “Modular Self-reconfigurable Robot Systems: Challenges and Opportunities for the Future,” IEEE Robotics & Automation Magazine, vol. 14, no. 1, pp. 43–52, Mar. 2007.
BibTeX
@article{yim2007modular-self-reconfigurable-robot-systems, abstract = "The field of modular self-reconfigurable robotic systems addresses the design, fabrication, motion planning, and control of autonomous kinematic machines with variable morphology. Beyond conventional actuation, sensing, and control typically found in fixed-morphology robots, self-reconfigurable robots are also able to deliberately change their own shape by rearranging the connectivity of their parts in order to adapt to new circumstances, perform new tasks, or recover from damage. Over the last two decades, this field has advanced from proof-of-concept systems to elaborate physical implementations and simulations. The goal of this article is to outline some of this progress and identify key challenges and opportunities that lay ahead.", author = "Yim, Mark and Shen, Wei-Min and Salemi, Benham and Rus, Daniela and Moll, Mark and Lipson, Hod and Klavins, Eric", doi = "10.1109/MRA.2007.339623", journal = "{IEEE} Robotics \& Automation Magazine", month = mar, number = "1", pages = "43--52", title = "Modular Self-reconfigurable Robot Systems: Challenges and Opportunities for the Future", volume = "14", year = "2007" }Abstract
The field of modular self-reconfigurable robotic systems addresses the design, fabrication, motion planning, and control of autonomous kinematic machines with variable morphology. Beyond conventional actuation, sensing, and control typically found in fixed-morphology robots, self-reconfigurable robots are also able to deliberately change their own shape by rearranging the connectivity of their parts in order to adapt to new circumstances, perform new tasks, or recover from damage. Over the last two decades, this field has advanced from proof-of-concept systems to elaborate physical implementations and simulations. The goal of this article is to outline some of this progress and identify key challenges and opportunities that lay ahead.
- B. Y. Chen, D. H. Bryant, J. H. Bylund, A. E. Cruess, D. M. Kristensen, V. Y. Fofanov, M. Moll, M. Kimmel, O. Lichtarge, and L. E. Kavraki, “Representations of Structural Motifs for Protein Function Prediction,” in 15th Annual Intl. Conf. on Intelligent Systems for Molecular Biology (ISMB) & 6th European Conf. on Comp. Bio. (ECCB), Vienna, Austria, 2007.
BibTeX
@inproceedings{chen2007representations-of-structural-motifs-for-protein, address = "Vienna, Austria", author = "Chen, Brian Y. and Bryant, Drew H. and Bylund, Joseph H. and Cruess, Amanda E. and Kristensen, David M. and Fofanov, Viacheslav Y. and Moll, Mark and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E.", booktitle = "15th Annual Intl.\ Conf.\ on Intelligent Systems for Molecular Biology (ISMB) \& 6th European Conf.\ on Comp.\ Bio.\ (ECCB)", title = "Representations of Structural Motifs for Protein Function Prediction", year = "2007" } - W.-M. Shen, B. Salemi, M. Moll, C. H. Chiu, J. Everist, F. Hou, N. Ranasinghe, and M. Rubenstein, “Multifunctional Behaviors of Reconfigurable SuperBot Modules,” in Proc. 2007 IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, 2007. Video
BibTeX
@inproceedings{shen2007multifunctional-and-reconfigurable-superbot-modules, abstract = "Superbot consists of Lego-like but autonomous robotic modules that can reconfigure into different systems for different tasks. Examples of configurable systems include rolling tracks or wheels (for efficient travel), spiders or centipedes (for climbing), snakes (for burrowing in ground), and climbers (for inspection and repair in space). This video shows several configurations and behaviors that are new for modular and reconfigurable robots. Each SuperBot module is a complete robotic system and has a power supply, micro- controllers, sensors, communication, three degrees of freedom, and six connecting faces (front, back, left, right, up and down) to dynamically connect to other modules. This design allows flexible bending, docking, and continuous rotation. A single module can move forward, back, left, right, flip-over, and rotate as a wheel. Modules can communication with each other for totally distributed control and can support arbitrary module reshuffling during their operation. The modules have both internal and external sensors for monitoring self-status and environmental parameters. They can form arbitrary configurations (graphs) and can control these configurations for different functionality such as locomotion, manipulation, and self-repair. This video shows the latest status the SuperBot modules and all these behaviors were made in just one week. The fact that SuperBot can achieve so much in so short a time demonstrates the unique value of modular, multifunctional and self-reconfigurable robots.", author = "Shen, Wei-Min and Salemi, Behnam and Moll, Mark and Chiu, Chi Ho and Everist, Jacob and Hou, Feili and Ranasinghe, Nadeesha and Rubenstein, Michael", booktitle = "Proc.\ 2007 {IEEE/RSJ} Intl.\ Conf.\ on Intelligent Robots and Systems", doi = "10.1109/IROS.2007.4399001", note = "\href{http://www.isi.edu/robots/superbot/movies/SuperBot.mov}{Video}", pubtype = "Other", title = "Multifunctional Behaviors of Reconfigurable {SuperBot} Modules", year = "2007" }Abstract
Superbot consists of Lego-like but autonomous robotic modules that can reconfigure into different systems for different tasks. Examples of configurable systems include rolling tracks or wheels (for efficient travel), spiders or centipedes (for climbing), snakes (for burrowing in ground), and climbers (for inspection and repair in space). This video shows several configurations and behaviors that are new for modular and reconfigurable robots. Each SuperBot module is a complete robotic system and has a power supply, micro- controllers, sensors, communication, three degrees of freedom, and six connecting faces (front, back, left, right, up and down) to dynamically connect to other modules. This design allows flexible bending, docking, and continuous rotation. A single module can move forward, back, left, right, flip-over, and rotate as a wheel. Modules can communication with each other for totally distributed control and can support arbitrary module reshuffling during their operation. The modules have both internal and external sensors for monitoring self-status and environmental parameters. They can form arbitrary configurations (graphs) and can control these configurations for different functionality such as locomotion, manipulation, and self-repair. This video shows the latest status the SuperBot modules and all these behaviors were made in just one week. The fact that SuperBot can achieve so much in so short a time demonstrates the unique value of modular, multifunctional and self-reconfigurable robots.
- B. Y. Chen, D. H. Bryant, V. Y. Fofanov, D. M. Kristensen, M. Moll, M. Kimmel, O. Lichtarge, and L. E. Kavraki, “Geometry-inspired Optimization Methods for Structural Motifs for Protein Function Prediction,” in Automated Function Prediction Meeting (AFP), Vienna, Austria, 2007.
BibTeX
@inproceedings{chen2007geometry-inspired-optimization-methods-for-structural, address = "Vienna, Austria", author = "Chen, Brian Y. and Bryant, Drew H. and Fofanov, Viacheslav Y. and Kristensen, David M. and Moll, Mark and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E.", booktitle = "Automated Function Prediction Meeting (AFP)", title = "Geometry-inspired Optimization Methods for Structural Motifs for Protein Function Prediction", year = "2007" }
2006
- M. Moll, P. Will, M. Krivokon, and W.-M. Shen, “Distributed Control of the Center of Mass of a Modular Robot,” in Proc. 2006 IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, Beijing, China, 2006, pp. 4710–4715.
BibTeX
@inproceedings{moll2006distributed-control-of-the-center-of-mass, abstract = "We present a distributed controller for the center of mass of a modular robot. This is useful for locomotion of a modular robot over uneven and unknown terrain. By controlling the center of mass, a robot can prevent itself from falling over. We present a distributed and decentralized algorithm that computes the mass properties of the robot. Additionally, each module also computes the mass properties of the modules that are directly or indirectly connected to each of its connectors. With this information, each module can independently steer the center of mass towards a desired position by adjusting its joint positions. We present simulation results that show the feasibility of the approach.", address = "Beijing, China", author = "Moll, Mark and Will, Peter and Krivokon, Maks and Shen, Wei-Min", booktitle = "Proc.\ 2006 {IEEE/RSJ} Intl.\ Conf.\ on Intelligent Robots and Systems", doi = "10.1109/IROS.2006.282261", month = oct, pages = "4710--4715", title = "Distributed Control of the Center of Mass of a Modular Robot", year = "2006" }Abstract
We present a distributed controller for the center of mass of a modular robot. This is useful for locomotion of a modular robot over uneven and unknown terrain. By controlling the center of mass, a robot can prevent itself from falling over. We present a distributed and decentralized algorithm that computes the mass properties of the robot. Additionally, each module also computes the mass properties of the modules that are directly or indirectly connected to each of its connectors. With this information, each module can independently steer the center of mass towards a desired position by adjusting its joint positions. We present simulation results that show the feasibility of the approach.
- B. Salemi, M. Moll, and W.-M. Shen, “SUPERBOT: A Deployable, Multi-Functional, and Modular Self-Reconfigurable Robotic System,” in Proc. 2006 IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, Beijing, China, 2006, pp. 3636–3641.
BibTeX
@inproceedings{salemi2006superbot, abstract = "Self-reconfigurable robots are modular robots that can autonomously change their shape and size to meet specific operational demands. Recently, there has been a great interest in using self-reconfigurable robots in applications such as reconnaissance, rescue missions, and space applications. Designing and controlling self-reconfigurable robots is a difficult task. Hence, the research has primarily been focused on developing systems that can function in a controlled environment. This paper presents a novel self-reconfigurable robotic system called SuperBot, which addresses the challenges of building and controlling deployable self-reconfigurable robots. Six prototype modules have been built and preliminary experimental results demonstrate that SuperBot is a flexible and powerful system that can be used in challenging real-world applications.", address = "Beijing, China", author = "Salemi, Behnam and Moll, Mark and Shen, Wei-Min", booktitle = "Proc.\ 2006 {IEEE/RSJ} Intl.\ Conf.\ on Intelligent Robots and Systems", doi = "10.1109/IROS.2006.281719", month = oct, pages = "3636--3641", title = "{SUPERBOT}: A Deployable, Multi-Functional, and Modular Self-Reconfigurable Robotic System", year = "2006" }Abstract
Self-reconfigurable robots are modular robots that can autonomously change their shape and size to meet specific operational demands. Recently, there has been a great interest in using self-reconfigurable robots in applications such as reconnaissance, rescue missions, and space applications. Designing and controlling self-reconfigurable robots is a difficult task. Hence, the research has primarily been focused on developing systems that can function in a controlled environment. This paper presents a novel self-reconfigurable robotic system called SuperBot, which addresses the challenges of building and controlling deployable self-reconfigurable robots. Six prototype modules have been built and preliminary experimental results demonstrate that SuperBot is a flexible and powerful system that can be used in challenging real-world applications.
- M. Moll and L. E. Kavraki, “Path Planning for Deformable Linear Objects,” IEEE Trans. on Robotics, vol. 22, no. 4, pp. 625–636, Aug. 2006.
BibTeX
@article{moll2006path-planning-for-deformable-linear, abstract = "We present a new approach to path planning for deformable linear (one-dimensional) objects such as flexible wires. We introduce a method for efficiently computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. By restricting the planner to minimal-energy curves, the execution of a path becomes easier. Our curve representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. This planner can be used as a powerful local planner in a sampling-based roadmap method. This makes it possible to compute a roadmap of the entire ``shape space,'' which is not possible with previous approaches. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in cable routing, and motion planning for surgical suturing and snake-like robots.", author = "Moll, Mark and Kavraki, Lydia E.", doi = "10.1109/TRO.2006.878933", journal = "{IEEE} Trans.\ on Robotics", month = aug, number = "4", pages = "625--636", title = "Path Planning for Deformable Linear Objects", volume = "22", year = "2006" }Abstract
We present a new approach to path planning for deformable linear (one-dimensional) objects such as flexible wires. We introduce a method for efficiently computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. By restricting the planner to minimal-energy curves, the execution of a path becomes easier. Our curve representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. This planner can be used as a powerful local planner in a sampling-based roadmap method. This makes it possible to compute a roadmap of the entire “shape space,” which is not possible with previous approaches. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in cable routing, and motion planning for surgical suturing and snake-like robots.
- P. Das, M. Moll, H. Stamati, L. E. Kavraki, and C. Clementi, “Low-dimensional, free-energy landscapes of protein-folding reactions by nonlinear dimensionality reduction,” Proc. Natl. Acad. of Science USA, vol. 103, no. 26, pp. 9885–9890, Jun. 2006.
BibTeX
@article{das2006low-dimensional-free-energy-landscapes, abstract = "The definition of reaction coordinates for the characterization of a protein-folding reaction has long been a controversial issue, even for the ``simple'' case in which one single free-energy barrier separates the folded and unfolded ensemble. We propose a general approach to this problem to obtain a few collective coordinates by using nonlinear dimensionality reduction. We validate the usefulness of this method by characterizing the folding landscape associated with a coarse-grained protein model of src homology 3 as sampled by molecular dynamics simulations. The folding free-energy landscape projected on the few relevant coordinates emerging from the dimensionality reduction can correctly identify the transition-state ensemble of the reaction. The first embedding dimension efficiently captures the evolution of the folding process along the main folding route. These results clearly show that the proposed method can efficiently find a low-dimensional representation of a complex process such as protein folding.", author = "Das, Payel and Moll, Mark and Stamati, Hernan and Kavraki, Lydia E. and Clementi, Cecilia", doi = "10.1073/pnas.0603553103", journal = "Proc.\ Natl.\ Acad.\ of Science USA", keywords = "reaction coordinate, transition state, manifold, embedding, ISOMAP, ScIMAP", month = jun, number = "26", pages = "9885--9890", pmcid = "PMC1502548", pmid = "16785435", title = "Low-dimensional, free-energy landscapes of protein-folding reactions by nonlinear dimensionality reduction", volume = "103", year = "2006" }Abstract
The definition of reaction coordinates for the characterization of a protein-folding reaction has long been a controversial issue, even for the “simple” case in which one single free-energy barrier separates the folded and unfolded ensemble. We propose a general approach to this problem to obtain a few collective coordinates by using nonlinear dimensionality reduction. We validate the usefulness of this method by characterizing the folding landscape associated with a coarse-grained protein model of src homology 3 as sampled by molecular dynamics simulations. The folding free-energy landscape projected on the few relevant coordinates emerging from the dimensionality reduction can correctly identify the transition-state ensemble of the reaction. The first embedding dimension efficiently captures the evolution of the folding process along the main folding route. These results clearly show that the proposed method can efficiently find a low-dimensional representation of a complex process such as protein folding.
2005
- M. Moll and L. E. Kavraki, “Path Planning for Variable Resolution Minimal-Energy Curves of Constant Length,” in Proc. 2005 IEEE Intl. Conf. on Robotics and Automation, 2005, pp. 2142–2147.
BibTeX
@inproceedings{moll-kavraki2005path-plann-variab-resol, abstract = "We present a new approach to path planning for flexible wires. We introduce a method for computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. The representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in motion planning for surgical suturing and snake-like robots.", author = "Moll, Mark and Kavraki, Lydia E.", booktitle = "Proc.\ 2005 {IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ROBOT.2005.1570428", keywords = "path planning, minimal-energy curves, subdivision", pages = "2142--2147", title = "Path Planning for Variable Resolution Minimal-Energy Curves of Constant Length", year = "2005" }Abstract
We present a new approach to path planning for flexible wires. We introduce a method for computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. The representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in motion planning for surgical suturing and snake-like robots.
2004
- M. Moll and M. A. Erdmann, “Reconstructing the Shape and Motion of Unknown Objects with Active Tactile Sensors,” in Algorithmic Foundations of Robotics V, J.-D. Boissonnat, J. Burdick, K. Goldberg, and S. Hutchinson, Eds. Springer Verlag, 2004, pp. 293–310.
BibTeX
@incollection{moll2004reconstructing-the-shape-and-motion-of-unknown, abstract = "We present a method to simultaneously reconstruct the shape and motion of an unknown smooth convex object. The object is manipulated by planar palms covered with tactile elements. The shape and dynamics of the object can be expressed as a function of the sensor values and the motion of the palms. We present a brief review of previous results for the planar case. In this paper we show that the 3D case is fundamentally different from the planar case, due to increased tangent dimensionality. The main contribution of this paper is a shape-dynamics analysis in 3D, and the synthesis of shape approximation methods via reconstructed contact point curves.", author = "Moll, Mark and Erdmann, Michael A.", booktitle = "Algorithmic Foundations of Robotics V", doi = "10.1007/b80173", editor = "Boissonnat, Jean-Daniel and Burdick, Joel and Goldberg, Ken and Hutchinson, Seth", keywords = "tactile sensing, shape reconstruction, nonprehensile manipulation, contact kinematics", pages = "293--310", publisher = "Springer Verlag", series = "Springer Tracts in Advanced Robotics", title = "Reconstructing the Shape and Motion of Unknown Objects with Active Tactile Sensors", year = "2004" }Abstract
We present a method to simultaneously reconstruct the shape and motion of an unknown smooth convex object. The object is manipulated by planar palms covered with tactile elements. The shape and dynamics of the object can be expressed as a function of the sensor values and the motion of the palms. We present a brief review of previous results for the planar case. In this paper we show that the 3D case is fundamentally different from the planar case, due to increased tangent dimensionality. The main contribution of this paper is a shape-dynamics analysis in 3D, and the synthesis of shape approximation methods via reconstructed contact point curves.
- M. Moll and L. E. Kavraki, “Path Planning for Minimal Energy Curves of Constant Length,” in Proc. 2004 IEEE Intl. Conf. on Robotics and Automation, 2004, pp. 2826–2831.
BibTeX
@inproceedings{moll-kavraki2004path-plann-minim-energ, abstract = "In this paper we present a new path planning technique for a flexible wire. We first introduce a new parametrization designed to represent low-energy configurations. Based on this parametrization we can find curves that satisfy endpoint constraints. Next, we present three different techniques for minimizing energy within the self-motion manifold of the curve. We introduce a local planner to find smooth minimal energy deformations for these curves that can be used by a general path planning algorithm. Using a simplified model for obstacles, we can find minimal energy curves of fixed length that pass through specified tangents at given control points. Finally, we show that the parametrization introduced in this paper is a good approximation of true minimal energy curves. Our work has applications in surgical suturing and snake-like robots.", author = "Moll, Mark and Kavraki, Lydia E.", booktitle = "Proc.\ 2004 {IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ROBOT.2004.1307489", keywords = "path planning, curve parametrization, minimal energy curves", pages = "2826--2831", title = "Path Planning for Minimal Energy Curves of Constant Length", year = "2004" }Abstract
In this paper we present a new path planning technique for a flexible wire. We first introduce a new parametrization designed to represent low-energy configurations. Based on this parametrization we can find curves that satisfy endpoint constraints. Next, we present three different techniques for minimizing energy within the self-motion manifold of the curve. We introduce a local planner to find smooth minimal energy deformations for these curves that can be used by a general path planning algorithm. Using a simplified model for obstacles, we can find minimal energy curves of fixed length that pass through specified tangents at given control points. Finally, we show that the parametrization introduced in this paper is a good approximation of true minimal energy curves. Our work has applications in surgical suturing and snake-like robots.
- M. Moll, D. Schwarz, A. Heath, and L. E. Kavraki, “On Flexible Docking Using Expansive Search,” Rice University, Houston, TX, 04-443, 2004.
BibTeX
@techreport{moll2004dockin-flexib-ligan, abstract = "The activity of most drugs is regulated by the binding of one molecule (the ligand) to a pocket of another, usually larger, molecule, which is commonly a protein. This report describes a new approach to creating low-energy structures of flexible proteins to which ligands can be docked. The flexibility of molecules is encoded with thousands of parameters making the search for valid complexes a formidable problem. Our method takes into account the flexibility of the protein as this can be encoded by its major modes of motion. The output of the program consists of low-energy protein conformations that can then be docked with a ligand using a traditional docking program. We employ a robotics-based approach for exploring the conformational space of the protein. Our long term goal is to develop an efficient, accurate, and automated algorithm that will be used to screen large databases of molecules for novel therapeutics.", address = "Houston, TX", author = "Moll, Mark and Schwarz, David and Heath, Allison and Kavraki, Lydia E.", institution = "Rice University", number = "04-443", pubtype = "Other", title = "On Flexible Docking Using Expansive Search", year = "2004" }Abstract
The activity of most drugs is regulated by the binding of one molecule (the ligand) to a pocket of another, usually larger, molecule, which is commonly a protein. This report describes a new approach to creating low-energy structures of flexible proteins to which ligands can be docked. The flexibility of molecules is encoded with thousands of parameters making the search for valid complexes a formidable problem. Our method takes into account the flexibility of the protein as this can be encoded by its major modes of motion. The output of the program consists of low-energy protein conformations that can then be docked with a ligand using a traditional docking program. We employ a robotics-based approach for exploring the conformational space of the protein. Our long term goal is to develop an efficient, accurate, and automated algorithm that will be used to screen large databases of molecules for novel therapeutics.
2002
- M. Moll, “Shape Reconstruction Using Active Tactile Sensors,” PhD thesis, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, 2002.
BibTeX
@phdthesis{moll2002shape-recon-using-activ, abstract = "We present a new method to reconstruct the shape of an unknown object using tactile sensors, without requiring object immobilization. Instead, sensing and nonprehensile manipulation occur simultaneously. The robot infers the shape, motion and center of mass of the object based on the motion of the contact points as measured by the tactile sensors. This allows for a natural, continuous interaction between manipulation and sensing. We analyze the planar case first by assuming quasistatic dynamics, and present simulation results and experimental results obtained using this analysis. We extend this analysis to the full dynamics and prove observability of the nonlinear system describing the shape and motion of the object being manipulated. In our simulations, a simple observer based on Newton's method for root finding performs really well. Using the same framework we can also describe the shape and dynamics of three-dimensional objects. However, there are some fundamental differences between the planar and three-dimensional case, due to increased tangent dimensionality. Also, perfect global shape reconstruction is impossible in the 3D case, but it is almost trivial to obtain upper and lower bounds on the shape. The 3D shape reconstruction method has also been implemented and we present some simulation results.", address = "Pittsburgh, PA", author = "Moll, Mark", keywords = "tactile sensing, shape reconstruction, nonprehensile manipulation", month = jul, pubtype = "Other", school = "Computer Science Department, Carnegie Mellon University", title = "Shape Reconstruction Using Active Tactile Sensors", year = "2002" }Abstract
We present a new method to reconstruct the shape of an unknown object using tactile sensors, without requiring object immobilization. Instead, sensing and nonprehensile manipulation occur simultaneously. The robot infers the shape, motion and center of mass of the object based on the motion of the contact points as measured by the tactile sensors. This allows for a natural, continuous interaction between manipulation and sensing. We analyze the planar case first by assuming quasistatic dynamics, and present simulation results and experimental results obtained using this analysis. We extend this analysis to the full dynamics and prove observability of the nonlinear system describing the shape and motion of the object being manipulated. In our simulations, a simple observer based on Newton’s method for root finding performs really well. Using the same framework we can also describe the shape and dynamics of three-dimensional objects. However, there are some fundamental differences between the planar and three-dimensional case, due to increased tangent dimensionality. Also, perfect global shape reconstruction is impossible in the 3D case, but it is almost trivial to obtain upper and lower bounds on the shape. The 3D shape reconstruction method has also been implemented and we present some simulation results.
- M. Moll and M. A. Erdmann, “Manipulation of Pose Distributions,” Intl. J. of Robotics Research, vol. 21, no. 3, pp. 277–292, Mar. 2002.
BibTeX
@article{moll-erdmann2002manip-pose-distr, abstract = "For assembly tasks parts often have to be oriented before they can be put in an assembly. The results presented in this paper are a component of the automated design of parts orienting devices. The focus is on orienting parts with minimal sensing and manipulation. We present a new approach to parts orienting through the manipulation of pose distributions. Through dynamic simulation we can determine the pose distribution for an object being dropped from an arbitrary height on an arbitrary surface. By varying the drop height and the shape of the support surface we can find the initial conditions that will result in a pose distribution with minimal entropy. We are trying to uniquely orient a part with high probability just by varying the initial conditions. We will derive a condition on the pose and velocity of a simple planar object in contact with a sloped surface that will allow us to quickly determine the final resting configuration of the object. This condition can then be used to quickly compute the pose distribution. We also present simulation and experimental results that show how dynamic simulation can be used to find optimal shapes and drop heights for a given part.", author = "Moll, Mark and Erdmann, Michael A.", doi = "10.1177/027836402320556449", journal = "Intl.\ J.\ of Robotics Research", keywords = "pose distributions, parts orienting, dynamic simulation", month = mar, number = "3", pages = "277--292", title = "Manipulation of Pose Distributions", volume = "21", year = "2002" }Abstract
For assembly tasks parts often have to be oriented before they can be put in an assembly. The results presented in this paper are a component of the automated design of parts orienting devices. The focus is on orienting parts with minimal sensing and manipulation. We present a new approach to parts orienting through the manipulation of pose distributions. Through dynamic simulation we can determine the pose distribution for an object being dropped from an arbitrary height on an arbitrary surface. By varying the drop height and the shape of the support surface we can find the initial conditions that will result in a pose distribution with minimal entropy. We are trying to uniquely orient a part with high probability just by varying the initial conditions. We will derive a condition on the pose and velocity of a simple planar object in contact with a sloped surface that will allow us to quickly determine the final resting configuration of the object. This condition can then be used to quickly compute the pose distribution. We also present simulation and experimental results that show how dynamic simulation can be used to find optimal shapes and drop heights for a given part.
- M. Moll, K. Goldberg, M. A. Erdmann, and R. Fearing, “Aligning Parts for Micro Assemblies,” Assembly Automation, vol. 22, no. 1, pp. 46–54, Feb. 2002.
BibTeX
@article{moll2002align-parts-micro-assem, abstract = "Orienting parts that measure only a few micrometers in diameter introduces several challenges that need not be considered at the macro-scale. First, there are several kinds of sticking effects due to Van der Waals forces and static electricity which complicate hand-off motions and release of a part. Second, the degrees of freedom of micro-manipulators are limited. This paper proposes a pair of manipulation primitives and a complete algorithm that addresses these challenges. We will show that a sequence of these two manipulation primitives can uniquely orient any asymmetric part while maintaining contact without sensing. This allows us to apply the same plan to many (identical) parts simultaneously. For asymmetric parts we can find a plan of length O(n) in O(n) time that orients the part, where n is the number of vertices.", author = "Moll, Mark and Goldberg, Ken and Erdmann, Michael A. and Fearing, Ron", doi = "10.1108/01445150210416673", journal = "Assembly Automation", keywords = "micromanipulation, parts orienting, parts feeding, rolling", month = feb, number = "1", pages = "46--54", title = "Aligning Parts for Micro Assemblies", volume = "22", year = "2002" }Abstract
Orienting parts that measure only a few micrometers in diameter introduces several challenges that need not be considered at the macro-scale. First, there are several kinds of sticking effects due to Van der Waals forces and static electricity which complicate hand-off motions and release of a part. Second, the degrees of freedom of micro-manipulators are limited. This paper proposes a pair of manipulation primitives and a complete algorithm that addresses these challenges. We will show that a sequence of these two manipulation primitives can uniquely orient any asymmetric part while maintaining contact without sensing. This allows us to apply the same plan to many (identical) parts simultaneously. For asymmetric parts we can find a plan of length O(n) in O(n) time that orients the part, where n is the number of vertices.
- M. Moll and M. A. Erdmann, “Dynamic Shape Reconstruction Using Tactile Sensors,” in Proc. 2002 IEEE Intl. Conf. on Robotics and Automation, 2002, pp. 1636–1641.
BibTeX
@inproceedings{moll-erdmann2002dynam-shape-recon-using, abstract = "We present new results on reconstruction of the shape and motion of an unknown object using tactile sensors without requiring object immobilization. A robot manipulates the object with two flat palms covered with tactile sensors. We model the full dynamics and prove local observability of the shape, motion and center of mass of the object based on the motion of the contact points as measured by the tactile sensors.", author = "Moll, Mark and Erdmann, Michael A.", booktitle = "Proc.\ 2002 {IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ROBOT.2002.1014777", keywords = "shape reconstruction, tactile sensing, observability", pages = "1636--1641", title = "Dynamic Shape Reconstruction Using Tactile Sensors", year = "2002" }Abstract
We present new results on reconstruction of the shape and motion of an unknown object using tactile sensors without requiring object immobilization. A robot manipulates the object with two flat palms covered with tactile sensors. We model the full dynamics and prove local observability of the shape, motion and center of mass of the object based on the motion of the contact points as measured by the tactile sensors.
- M. Moll, K. Goldberg, M. A. Erdmann, and R. Fearing, “Orienting Micro-Scale Parts with Squeeze and Roll Primitives,” in Proc. 2002 IEEE Intl. Conf. on Robotics and Automation, 2002, pp. 1931–1936.
BibTeX
@inproceedings{moll2002orien-micro-scale-parts, abstract = "Orienting parts that measure only a few micrometers in diameter introduces several challenges that need not be considered at the macro-scale. First, there are several kinds of sticking effects due to Van der Waals forces and static electricity which complicate hand-off motions and release of a part. Second, the degrees of freedom of micro-manipulators are limited. This paper proposes a pair of manipulation primitives and a complete algorithm that addresses these challenges. We will show that a sequence of these two manipulation primitives can uniquely orient any asymmetric part while maintaining contact without sensing. This allows us to apply the same plan to many (identical) parts simultaneously. For asymmetric parts we can find a plan of length O(n) in O(n) time that orients the part, where n is the number of vertices.", author = "Moll, Mark and Goldberg, Ken and Erdmann, Michael A. and Fearing, Ron", booktitle = "Proc.\ 2002 {IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ROBOT.2002.1014823", keywords = "micromanipulation, parts orienting, rolling", pages = "1931--1936", title = "Orienting Micro-Scale Parts with Squeeze and Roll Primitives", year = "2002" }Abstract
Orienting parts that measure only a few micrometers in diameter introduces several challenges that need not be considered at the macro-scale. First, there are several kinds of sticking effects due to Van der Waals forces and static electricity which complicate hand-off motions and release of a part. Second, the degrees of freedom of micro-manipulators are limited. This paper proposes a pair of manipulation primitives and a complete algorithm that addresses these challenges. We will show that a sequence of these two manipulation primitives can uniquely orient any asymmetric part while maintaining contact without sensing. This allows us to apply the same plan to many (identical) parts simultaneously. For asymmetric parts we can find a plan of length O(n) in O(n) time that orients the part, where n is the number of vertices.
2001
- M. Moll and M. A. Erdmann, “Reconstructing Shape from Motion Using Tactile Sensors,” in Proc. 2001 IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, Maui, HI, 2001, pp. 691–700.
BibTeX
@inproceedings{moll-erdmann2001recon-shape-motion-using, abstract = "We present a new method to reconstruct the shape of an unknown object using tactile sensors without requiring object immobilization. Instead, the robot manipulates the object without prehension. The robot infers the shape, motion and center of mass of the object based on the motion of the contact points as measured by tactile sensors. Our analysis is supported by simulation and experimental results.", address = "Maui, HI", author = "Moll, Mark and Erdmann, Michael A.", booktitle = "Proc.\ 2001 {IEEE/RSJ} Intl.\ Conf.\ on Intelligent Robots and Systems", doi = "10.1109/IROS.2001.976250", keywords = "tactile sensing, shape reconstruction, contact kinematics", month = oct, pages = "691--700", title = "Reconstructing Shape from Motion Using Tactile Sensors", year = "2001" }Abstract
We present a new method to reconstruct the shape of an unknown object using tactile sensors without requiring object immobilization. Instead, the robot manipulates the object without prehension. The robot infers the shape, motion and center of mass of the object based on the motion of the contact points as measured by tactile sensors. Our analysis is supported by simulation and experimental results.
- M. Moll and M. A. Erdmann, “Shape Reconstruction in a Planar Dynamic Environment,” Dept. of Computer Science, Carnegie Mellon University, CMU-CS-01-107, 2001.
BibTeX
@techreport{moll-erdmann2001shape-recon-planar-dynam, abstract = "We present a a new method to reconstruct the shape of an unknown object using tactile sensors, without requiring object immobilization. Instead, sensing and nonprehensile manipulation occur simultaneously. The robot infers the shape, motion and center of mass of the object based on the motion of the contact points as measured by the tactile sensors. We present analytic results and simulation results assuming quasistatic dynamics. We prove that the shape and motion are observable in both the quasistatic and the fully dynamic case.", author = "Moll, Mark and Erdmann, Michael A.", institution = "Dept. of Computer Science, Carnegie Mellon University", keywords = "tactile reconstruction, contact kinematics, nonlinear observer theory, tactile sensing", number = "CMU-CS-01-107", pubtype = "Other", title = "Shape Reconstruction in a Planar Dynamic Environment", year = "2001" }Abstract
We present a a new method to reconstruct the shape of an unknown object using tactile sensors, without requiring object immobilization. Instead, sensing and nonprehensile manipulation occur simultaneously. The robot infers the shape, motion and center of mass of the object based on the motion of the contact points as measured by the tactile sensors. We present analytic results and simulation results assuming quasistatic dynamics. We prove that the shape and motion are observable in both the quasistatic and the fully dynamic case.
- M. Moll and M. A. Erdmann, “Manipulation of Pose Distributions,” in Algorithmic and Computational Robotics: New Directions, B. R. Donald, K. M. Lynch, and D. Rus, Eds. A. K. Peters, 2001, pp. 127–141.
BibTeX
@incollection{moll-erdmann2001manip-pose-distr, abstract = "For assembly tasks parts often have to be oriented before they can be put in an assembly. The results presented in this paper are a component of the automated design of parts orienting devices. The focus is on orienting parts with minimal sensing and manipulation. We present a new approach to parts orienting through the manipulation of pose distributions. Through dynamic simulation we can determine the pose distribution for an object being dropped from an arbitrary height on an arbitrary surface. By varying the drop height and the shape of the support surface we can find the initial conditions that will result in a pose distribution with minimal entropy. We are trying to uniquely orient a part with high probability just by varying the initial conditions. We will derive a condition on the pose and velocity of an object in contact with a sloped surface that will allow us to quickly determine the final resting configuration of the object. This condition can then be used to quickly compute the pose distribution. We also present simulation and experimental results that show how dynamic simulation can be used to find optimal shapes and drop heights for a given part.", author = "Moll, Mark and Erdmann, Michael A.", booktitle = "Algorithmic and Computational Robotics: New Directions", editor = "Donald, Bruce R. and Lynch, Kevin M. and Rus, Daniela", keywords = "pose distributions, parts orienting, dynamic simulation", pages = "127--141", publisher = "A. K. Peters", title = "Manipulation of Pose Distributions", url = "http://www.crcpress.com/product/isbn/9781568811253", year = "2001" }Abstract
For assembly tasks parts often have to be oriented before they can be put in an assembly. The results presented in this paper are a component of the automated design of parts orienting devices. The focus is on orienting parts with minimal sensing and manipulation. We present a new approach to parts orienting through the manipulation of pose distributions. Through dynamic simulation we can determine the pose distribution for an object being dropped from an arbitrary height on an arbitrary surface. By varying the drop height and the shape of the support surface we can find the initial conditions that will result in a pose distribution with minimal entropy. We are trying to uniquely orient a part with high probability just by varying the initial conditions. We will derive a condition on the pose and velocity of an object in contact with a sloped surface that will allow us to quickly determine the final resting configuration of the object. This condition can then be used to quickly compute the pose distribution. We also present simulation and experimental results that show how dynamic simulation can be used to find optimal shapes and drop heights for a given part.
2000
- M. Moll and M. A. Erdmann, “Uncertainty Reduction Using Dynamics,” in Proc. 2000 IEEE Intl. Conf. on Robotics and Automation, San Francisco, California, 2000, pp. 3673–3680.
BibTeX
@inproceedings{moll-erdmann2000uncer-reduc-using-dynam, abstract = "For assembly tasks parts often have to be oriented before they can be put in an assembly. The results presented in this paper are a component of the automated design of parts orienting devices. The focus is on orienting parts with minimal sensing and manipulation. We present a new approach to parts orienting through the manipulation of pose distributions. Through dynamic simulation we can determine the pose distribution for an object being dropped from an arbitrary height on an arbitrary surface. By varying the drop height and the shape of the support surface we can find the initial conditions that will result in a pose distribution with minimal entropy. We are trying to uniquely orient a part with high probability just by varying the initial conditions. We will derive a condition on the pose and velocity of an object in contact with a sloped surface that will allow us to quickly determine the final resting configuration of the object. This condition can then be used to quickly compute the pose distribution. We also show simulation and experimental results that confirm that our dynamic simulator can be used to find the true pose distribution of an object.", address = "San Francisco, California", author = "Moll, Mark and Erdmann, Michael A.", booktitle = "Proc.\ 2000 {IEEE} Intl.\ Conf.\ on Robotics and Automation", doi = "10.1109/ROBOT.2000.845304", keywords = "pose distributions, parts orienting, dynamic simulation", pages = "3673--3680", title = "Uncertainty Reduction Using Dynamics", year = "2000" }Abstract
For assembly tasks parts often have to be oriented before they can be put in an assembly. The results presented in this paper are a component of the automated design of parts orienting devices. The focus is on orienting parts with minimal sensing and manipulation. We present a new approach to parts orienting through the manipulation of pose distributions. Through dynamic simulation we can determine the pose distribution for an object being dropped from an arbitrary height on an arbitrary surface. By varying the drop height and the shape of the support surface we can find the initial conditions that will result in a pose distribution with minimal entropy. We are trying to uniquely orient a part with high probability just by varying the initial conditions. We will derive a condition on the pose and velocity of an object in contact with a sloped surface that will allow us to quickly determine the final resting configuration of the object. This condition can then be used to quickly compute the pose distribution. We also show simulation and experimental results that confirm that our dynamic simulator can be used to find the true pose distribution of an object.
1997
- M. Moll and R. Miikkulainen, “Convergence-Zone Episodic Memory: Analysis and Simulations,” Neural Networks, vol. 10, no. 6, pp. 1017–1036, Aug. 1997.
BibTeX
@article{moll-miikkulainen1997conver-zone-episod-memor, abstract = "Human episodic memory provides a seemingly unlimited storage for everyday experiences, and a retrieval system that allows us to access the experiences with partial activation of their components. The system is believed to consist of a fast, temporary storage in the hippocampus, and a slow, long-term storage within the neocortex. This paper presents a neural network model of the hippocampal episodic memory inspired by Damasio's idea of Convergence Zones. The model consists of a layer of perceptual feature maps and a binding layer. A perceptual feature pattern is coarse coded in the binding layer, and stored on the weights between layers. A partial activation of the stored features activates the binding pattern, which in turn reactivates the entire stored pattern. For many configurations of the model, a theoretical lower bound for the memory capacity can be derived, and it can be an order of magnitude or higher than the number of all units in the model, and several orders of magnitude higher than the number of binding-layer units. Computational simulations further indicate that the average capacity is an order of magnitude larger than the theoretical lower bound, and making the connectivity between layers sparser causes an even further increase in capacity. Simulations also show that if more descriptive binding patterns are used, the errors tend to be more plausible (patterns are confused with other similar patterns), with a slight cost in capacity. The convergence-zone episodic memory therefore accounts for the immediate storage and associative retrieval capability and large capacity of the hippocampal memory, and shows why the memory encoding areas can be much smaller than the perceptual maps, consist of rather coarse computational units, and be only sparsely connected to the perceptual maps.", author = "Moll, Mark and Miikkulainen, Risto", doi = "10.1016/S0893-6080(97)00016-6", journal = "Neural Networks", month = aug, number = "6", pages = "1017--1036", title = "Convergence-Zone Episodic Memory: Analysis and Simulations", volume = "10", year = "1997" }Abstract
Human episodic memory provides a seemingly unlimited storage for everyday experiences, and a retrieval system that allows us to access the experiences with partial activation of their components. The system is believed to consist of a fast, temporary storage in the hippocampus, and a slow, long-term storage within the neocortex. This paper presents a neural network model of the hippocampal episodic memory inspired by Damasio’s idea of Convergence Zones. The model consists of a layer of perceptual feature maps and a binding layer. A perceptual feature pattern is coarse coded in the binding layer, and stored on the weights between layers. A partial activation of the stored features activates the binding pattern, which in turn reactivates the entire stored pattern. For many configurations of the model, a theoretical lower bound for the memory capacity can be derived, and it can be an order of magnitude or higher than the number of all units in the model, and several orders of magnitude higher than the number of binding-layer units. Computational simulations further indicate that the average capacity is an order of magnitude larger than the theoretical lower bound, and making the connectivity between layers sparser causes an even further increase in capacity. Simulations also show that if more descriptive binding patterns are used, the errors tend to be more plausible (patterns are confused with other similar patterns), with a slight cost in capacity. The convergence-zone episodic memory therefore accounts for the immediate storage and associative retrieval capability and large capacity of the hippocampal memory, and shows why the memory encoding areas can be much smaller than the perceptual maps, consist of rather coarse computational units, and be only sparsely connected to the perceptual maps.
1996
- M. Moll, “Mapping Science: Methods and Tools for the Automatic Creation of Semantic Maps of Large Corpora,” Centre for Science and Technology Studies (CWTS), Leiden, the Netherlands, Report CWTS 96-06, Aug. 1996. Research report to the Netherlands Organization for Scientific Research (NWO), Foundation for Economic and Socio-Cultural Sciences (ESR)
BibTeX
@techreport{moll1996mappin-scien, address = "Leiden, the Netherlands", author = "Moll, Mark", institution = "Centre for Science and Technology Studies (CWTS)", month = aug, note = "Research report to the Netherlands Organization for Scientific Research (NWO), Foundation for Economic and Socio-Cultural Sciences (ESR)", number = "96-06", pubtype = "Other", title = "Mapping Science: Methods and Tools for the Automatic Creation of Semantic Maps of Large Corpora", type = "Report CWTS", year = "1996" } - H. ter Doest, M. Moll, R. Bos, S. Van de Burgt, and A. Nijholt, “Language Engineering in Dialogue Systems,” Department of Computer Science, University of Twente, Memoranda Informatica 96-2, Jan. 1996.
BibTeX
@techreport{ter-doest1996language-engineering-in-dialogue-systems, abstract = "The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors, performs domain-specific morphological analysis is developed. A parser for typed unification grammars has been designed and implemented in C++; for description of the lexicon and the grammar a suitable specification language has been developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Finally we present a dialogue manager that is based on a finite state automaton; transitions in the automaton depend upon availability of information in utterances of the user. In order to keep track of the history of the dialogue, a context stack is constructed during the dialogue. The manager is implemented in Prolog. ", author = "{ter} Doest, Hugo and Moll, Mark and Bos, Ren{\'e} and Van de Burgt, Stan and Nijholt, Anton", institution = "Department of Computer Science, University of Twente", month = jan, number = "96-2", pubtype = "Other", title = "Language Engineering in Dialogue Systems", type = "Memoranda Informatica", year = "1996" }Abstract
The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors, performs domain-specific morphological analysis is developed. A parser for typed unification grammars has been designed and implemented in C++; for description of the lexicon and the grammar a suitable specification language has been developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Finally we present a dialogue manager that is based on a finite state automaton; transitions in the automaton depend upon availability of information in utterances of the user. In order to keep track of the history of the dialogue, a context stack is constructed during the dialogue. The manager is implemented in Prolog.
- H. ter Doest, M. Moll, R. Bos, S. Van de Burgt, and A. Nijholt, “Language Engineering in Dialogue Systems,” in Computers in Engineering Symposium, Houston, TX, 1996, pp. 68–79.
BibTeX
@inproceedings{ter1996languag-engin-dialog-system, abstract = "The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors, performs domain-specific morphological analysis is developed. A parser for typed unification grammars has been designed and implemented in C++; for description of the lexicon and the grammar a suitable specification language has been developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Finally we present a dialogue manager that is based on a finite state automaton; transitions in the automaton depend upon availability of information in utterances of the user. In order to keep track of the history of the dialogue, a context stack is constructed during the dialogue. The manager is implemented in Prolog. ", address = "Houston, TX", author = "{ter} Doest, Hugo and Moll, Mark and Bos, Ren{\'e} and Van de Burgt, Stan and Nijholt, Anton", booktitle = "Computers in Engineering Symposium", pages = "68--79", title = "Language Engineering in Dialogue Systems", year = "1996" }Abstract
The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors, performs domain-specific morphological analysis is developed. A parser for typed unification grammars has been designed and implemented in C++; for description of the lexicon and the grammar a suitable specification language has been developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Finally we present a dialogue manager that is based on a finite state automaton; transitions in the automaton depend upon availability of information in utterances of the user. In order to keep track of the history of the dialogue, a context stack is constructed during the dialogue. The manager is implemented in Prolog.
1995
- M. Moll, “Head-corner Parsing Using Typed Feature Structures,” Master's thesis, Department of Computer Science, University of Twente, 1995.
BibTeX
@mastersthesis{moll1995head-parsin-typed-featur, abstract = "In this report a description will be given of how typed feature structures can be specified. A specification language will be presented for the specification of types, words and grammar rules. An unification algorithm for typed feature structures as well as an algorithm to compute the least upper bound relation for a type lattice will be given. Finally, a head-corner parsing schema for typed feature structures will be presented.", author = "Moll, Mark", pubtype = "Other", school = "Department of Computer Science, University of Twente", title = "Head-corner Parsing Using Typed Feature Structures", year = "1995" }Abstract
In this report a description will be given of how typed feature structures can be specified. A specification language will be presented for the specification of types, words and grammar rules. An unification algorithm for typed feature structures as well as an algorithm to compute the least upper bound relation for a type lattice will be given. Finally, a head-corner parsing schema for typed feature structures will be presented.
- R. op den Akker, H. ter Doest, M. Moll, and A. Nijholt, “Parsing in Dialogue Systems using Typed Feature Structures,” Department of Computer Science, University of Twente, Memoranda Informatica 95-25, 1995.
BibTeX
@techreport{op1995parsin-dialog-system-typed-tr, abstract = "The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors and performs domain-specific morphological analysis has been developed. A parser for typed unification grammars is designed and implemented in C++; for description of the lexicon and the grammer a specialised specification language has been developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Research on these issues is carried out in the context of the Schisma project, a research project of the Parlevink group in linguistic engineering; participants in Schisma are KPN Research and the University of Twente. The aims of the Schisma project are twofold: both the accumulation of knowledge in the field of computational linguistics and the development of a natural language interfaced theatre information and booking system is envisaged. The Schisma project serves as a testbed for the development of the various language analysis modules necessary for dialogue systems.", author = "{op} den Akker, Rieks and {ter} Doest, Hugo and Moll, Mark and Nijholt, Anton", institution = "Department of Computer Science, University of Twente", number = "95-25", pubtype = "Other", title = "Parsing in Dialogue Systems using Typed Feature Structures", type = "Memoranda Informatica", url = "https://research.utwente.nl/en/publications/parsing-in-dialogue-systems-using-typed-feature-structures-2", year = "1995" }Abstract
The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors and performs domain-specific morphological analysis has been developed. A parser for typed unification grammars is designed and implemented in C++; for description of the lexicon and the grammer a specialised specification language has been developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Research on these issues is carried out in the context of the Schisma project, a research project of the Parlevink group in linguistic engineering; participants in Schisma are KPN Research and the University of Twente. The aims of the Schisma project are twofold: both the accumulation of knowledge in the field of computational linguistics and the development of a natural language interfaced theatre information and booking system is envisaged. The Schisma project serves as a testbed for the development of the various language analysis modules necessary for dialogue systems.
- R. op den Akker, H. ter Doest, M. Moll, and A. Nijholt, “Parsing in Dialogue Systems using Typed Feature Structures,” in Proceedings of the International Workshop on Parsing Technologies, Prague/Karlovy Vary, Czech Republic, 1995.
BibTeX
@inproceedings{op1995parsin-dialog-system-typed, abstract = "The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors, performs domain-specific morphological analysis is developed. A parser for typed unification grammars is designed and implemented in C++; for description of the lexicon and the grammer a specialised specification language is developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Research on these issues is carried out in the context of the Schisma project, a research project in linguistic engineering; participants in Schisma are KPN Research and the University of Twente.", address = "Prague/Karlovy Vary, Czech Republic", author = "{op} den Akker, Rieks and {ter} Doest, Hugo and Moll, Mark and Nijholt, Anton", booktitle = "Proceedings of the International Workshop on Parsing Technologies", title = "Parsing in Dialogue Systems using Typed Feature Structures", year = "1995" }Abstract
The analysis of natural language in the context of keyboard-driven dialogue systems is the central issue addressed in this paper. A module that corrects typing errors, performs domain-specific morphological analysis is developed. A parser for typed unification grammars is designed and implemented in C++; for description of the lexicon and the grammer a specialised specification language is developed. It is argued that typed unification grammars and especially the newly developed specification language are convenient formalisms for describing natural language use in dialogue systems. Research on these issues is carried out in the context of the Schisma project, a research project in linguistic engineering; participants in Schisma are KPN Research and the University of Twente.
1994
- M. Moll, R. Miikkulainen, and J. Abbey, “The Capacity of Convergence-Zone Episodic Memory,” in Proc. 12th Natl. Conf. on Artificial Intelligence (AAAI-94), Cambridge, MA, 1994, pp. 68–73.
BibTeX
@inproceedings{moll1994capac-conver-zone-episod, abstract = "Human episodic memory provides a seemingly unlimited storage for everyday experiences, and a retrieval system that allows us to access the experiences with partial activation of their components. This paper presents a neural network model of episodic memory inspired by Damasio's idea of Convergence Zones. The model consists of a layer of perceptual feature maps and a binding layer. A perceptual feature pattern is coarse coded in the binding layer, and stored on the weights between layers. A partial activation of the stored features activates the binding pattern which in turn reactivates the entire stored pattern. A worst-case analysis shows that with realistic-size layers, the memory capacity of the model is several times larger than the number of units in the model, and could account for the large capacity of human episodic memory.", address = "Cambridge, MA", author = "Moll, Mark and Miikkulainen, Risto and Abbey, Jonathan", booktitle = "Proc.\ 12th Natl. Conf.\ on Artificial Intelligence (AAAI-94)", pages = "68--73", publisher = "MIT Press", title = "The Capacity of Convergence-Zone Episodic Memory", url = "https://www.aaai.org/Papers/AAAI/1994/AAAI94-011.pdf", year = "1994" }Abstract
Human episodic memory provides a seemingly unlimited storage for everyday experiences, and a retrieval system that allows us to access the experiences with partial activation of their components. This paper presents a neural network model of episodic memory inspired by Damasio’s idea of Convergence Zones. The model consists of a layer of perceptual feature maps and a binding layer. A perceptual feature pattern is coarse coded in the binding layer, and stored on the weights between layers. A partial activation of the stored features activates the binding pattern which in turn reactivates the entire stored pattern. A worst-case analysis shows that with realistic-size layers, the memory capacity of the model is several times larger than the number of units in the model, and could account for the large capacity of human episodic memory.