Motion Analyze in Computational Biology and Molecular Modeling
In this topic of research, the goal is to define new methods for studying molecular motions and interactions. In our case we base our research on an original molecular modelling strategy recently investigated in the Robotics group at LAAS. This strategy relies on the combined use of efficient motion planning techniques issued from robotics research with energy-based models more classically used in molecular simulations. The interest of such combined strategy is to handle the complexity of macromolecular flexibility by exploiting the efficacy of a geometric conformational search as a filtering stage before subsequent energy refinements.
More specifically, I am currently working on the decomposition of the ligand/protein degrees of freedom in the ligand/protein docking problem. An other work in progress is the introduction of passive motion of the protein dofs according to the ligand motion.
All the computational methods are integrated in the software prototype Biomove3D currently developed at LAAS.
Motion Planner for Dynamically Changing Environments
Classically, motion planning algorithms are based on the exploration of
the configuration space of a mechanical system. Usually, this exploration is done through the use of sampling-based techniques.
I attempt to extend these methods by designing motion
planning algorithms dedicated to environments with both,
static and dynamic obstacles. One of my contributions is
to propose an hybrid planner (Dyn-planner)
that combines the PRM framework, originally designed for
solving multiple-query problems and that we extended for
operating in dynamic scenes, with improved diffusion
techniques designed to solve single queries without requiring any
preprocessing.
We proposed an approach in two streps: during an initialisation phase a roadmap valid according to static obstacles is built (ref). Then for each query, the roadmap is updated accoring to dynamic obstacles, using several mechanisms in order to make the method really efficient:
Finally, if no solution has been found, a reinforcement process is also proposed to include new cycles in the roadmap.
Diffusion Methods for Highly Constrained Problems
Sampling-based planners have solved difficult
problems in many applications of motion planning in recent
years. In particular, techniques based on the Rapidly-exploring
Random Trees (RRTs) have generated highly successful single-
query planners. Even though RRTs work well on many problems, they have weaknesses which cause them to explore slowly
when the sampling domain is not well adapted to the problem.
We have characterized these issues and proposed a
general framework for minimizing their effect. We developed
and implemented a simple new planner called Dynamic-Domain RRT (ref1, ref2) which shows significant
improvement over existing RRT-based planners. In the worst
cases, the performance appears to be only slightly worse in
comparison to the original RRT, and for many problems it
performs orders of magnitude better.
The key idea of the DD-RRT algorithm is to balance more adequately refinement and exploration behaviors of the RRT method in case of localy very constrained situations. To proceed such a balance, we limit the influence of the nodes closed to the obstacles to a specific region called Dynamic-Domain. An other variant has been aslo developped allowing an automatic adaptation of the size of the Dynamic-Domains during the search process and therefore avoiding any critical parameter tuning.
This new planner is the result of a fruitful collaboration with the MSL, Dep. of Computer Science of University of Illinois.
Capturing the Different Varieties of Free Configuration Space Paths
We proposed a new approach to sampling-based motion planning with
PRM methods in order to compute good quality roadmaps. These roadmaps encode the multiply connectedness of the Cspace inside low redundancy graphs, yet representative of the different varieties of free paths. Our method relies
on a notion of path deformability indicating wether or not a given path can be
continuously deformed to another existing one. By considering a simpler form
of deformation than the one allowed between homotopic paths, we propose a
method that extends the Visibility-PRM technique to construct compact
roadmaps that encode a richer and more suitable information than representative paths of the homotopy classes. The Path Deformation Roadmaps (PDR)
also contain additional useful cycles between paths in the same homotopy class
that can be hardly deformed into each other. Experiments show that our technique enables small roadmaps to reliably and ef ficiently capture the multiply-connectedness of the space in various problems.
In the case of partially dynamic environment, we also proposed in collaboration with the Dep. of Info. and Computing Sciences of Utrecht University a method to create robust roadmaps, facing the position changes of the obstacles.
