Publications

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. 3.1–3.27, 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 = "3.1--3.27",
      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. 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.

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

  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, 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,
      title = "Structure-Guided Selection of Specificity Determining
      		  Positions in the Human Kinome",
      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’ Conference (Guest Editorial),” 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. 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.

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

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

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

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

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

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

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

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

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

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

  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. 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"
    }

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

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

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

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

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.