Publications

2019

  1. 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. To appear.
    pdf publisher

    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, Narcis and Hern{\'a}ndez, Juan David and Carreras, Marc and Kavraki, Lydia",
      booktitle = "{IEEE} Intl.\ Conf.\ on Robotics and Automation",
      month = may,
      note = "To appear.",
      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.

  2. 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.
    pdf publisher

    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, Narc\'\is 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).

  3. 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, 2019. To appear.
    pdf publisher

    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 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",
      note = "To appear.",
      title = "Machine Learning Guided Atom Mapping of Metabolic Reactions",
      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.

2018

  1. Z. K. 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.
    pdf publisher

    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 K. 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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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).
    pdf publisher

    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.

  5. 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.
    pdf publisher

    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

  1. Z. K. Kingston, M. Moll, and L. E. Kavraki, “Decoupling Constraints from Sampling-Based Planners,” in Intl. Symp. on Robotics Research, 2017.
    pdf publisher

    BibTeX

    @inproceedings{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 K and Moll, Mark and Kavraki, Lydia E.",
      booktitle = "Intl.\ Symp.\ on Robotics Research",
      month = dec,
      title = "Decoupling Constraints from Sampling-Based Planners",
      year = "2017"
    }

    Abstract

    We present a general unifying framework for sampling-based motion planning under kinematic task constraints which enables a broad class of planners to compute plans that satisfy a given constraint function that encodes, e.g., loop closure, balance, and end-effector constraints. The framework decouples a planner’s method for exploration from constraint satisfaction by representing the implicit configuration space defined by a constraint function. We emulate three constraint satisfaction methodologies from the literature, and demonstrate the framework with a range of planners utilizing these constraint methodologies. Our results show that the appropriate choice of constrained satisfaction methodology depends on many factors, e.g., the dimension of the configuration space and implicit constraint manifold, and number of obstacles. Furthermore, we show that novel combinations of planners and constraint satisfaction methodologies can be more effective than previous approaches. The framework is also easily extended for novel planners and constraint spaces.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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.

  5. 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.
    pdf publisher

    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.

  6. 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.
    pdf publisher

    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

  1. S. Butler, M. Moll, and L. E. Kavraki, “A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints,” in Workshop on the Algorithmic Foundations of Robotics, 2016.
    pdf publisher

    BibTeX

    @inproceedings{butler2016a-general-algorithm-for-time-optimal-trajectory,
      abstract = "This paper presents a new algorithm which generates time-optimal
            trajectories given a path as input. The algorithm improves on previous
            approaches by generically handling a broader class of constraints on
            the dynamics. It eliminates the need for heuristics to select
            trajectory segments that are part of the optimal trajectory through an
            exhaustive, but efficient search. We also present an algorithm for
            computing all achievable velocities at the end of a path given an
            initial range of velocities. This algorithm effectively computes
            bundles of feasible trajectories for a given path and is a first step
            toward a new generation of more efficient kinodynamic motion planning
            algorithms. We present results for both algorithms using a simulated
            WAM arm with a Barrett hand subject to dynamics constraints on joint
            torque, joint velocity, momentum, and end effector velocity. The new
            algorithms are compared with a state-of-the-art alternative approach.",
      author = "Butler, Stephen and Moll, Mark and Kavraki, Lydia E.",
      booktitle = "Workshop on the Algorithmic Foundations of Robotics",
      month = dec,
      title = "A General Algorithm for Time-Optimal Trajectory Generation Subject
            to Minimum and Maximum Constraints",
      year = "2016"
    }

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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.

  5. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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.

  5. 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.
    pdf publisher

    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.

  6. 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.
    pdf publisher

    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.

  7. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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.

  5. 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.
    pdf publisher

    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.

  6. 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.
    pdf publisher

    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.

  7. 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.
    pdf publisher

    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.

  8. 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.
    pdf publisher

    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

  1. 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
    pdf publisher

    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).

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

2010

  1. M. Moll, D. H. Bryant, and L. E. Kavraki, “The LabelHash Algorithm for Substructure Matching,” BMC Bioinformatics, vol. 11, no. 555, Nov. 2010.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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.

2009

  1. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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"
    }
  2. 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.
    pdf publisher

    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.

  3. 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
    pdf publisher

    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"
    }
  4. 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.
    pdf publisher

    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/.

2007

  1. 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.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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",
      url = "http://www.iscb.org/uploaded/css/E108Moll.pdf",
      year = "2007"
    }
  4. 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.
    pdf publisher

    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",
      url = "http://biofunctionprediction.org/files/afp-biosap-2007-full-program.pdf",
      year = "2007"
    }
  5. 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
    pdf publisher

    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.

2006

  1. 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.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. M. Moll, D. Schwarz, A. Heath, and L. E. Kavraki, “On Flexible Docking Using Expansive Search,” Rice University, Houston, TX, 04-443, 2004.
    pdf publisher

    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

  1. M. Moll, “Shape Reconstruction Using Active Tactile Sensors,” PhD thesis, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, 2002.
    pdf publisher

    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.

  2. M. Moll and M. A. Erdmann, “Manipulation of Pose Distributions,” Intl. J. of Robotics Research, vol. 21, no. 3, pp. 277–292, Mar. 2002.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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.

  4. 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.
    pdf publisher

    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.

  5. 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.
    pdf publisher

    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.

2001

  1. 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.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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

  1. 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.
    pdf publisher

    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

  1. M. Moll and R. Miikkulainen, “Convergence-Zone Episodic Memory: Analysis and Simulations,” Neural Networks, vol. 10, no. 6, pp. 1017–1036, Aug. 1997.
    pdf publisher

    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

  1. 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)
    pdf publisher

    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"
    }
  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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

  1. M. Moll, “Head-corner Parsing Using Typed Feature Structures,” Master's thesis, Department of Computer Science, University of Twente, 1995.
    pdf publisher

    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.

  2. 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.
    pdf publisher

    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.

  3. 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.
    pdf publisher

    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 = "http://eprints.eemcs.utwente.nl/9891/",
      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.

1994

  1. 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.
    pdf publisher

    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.