Sampling-based algorithms for path-finding in continuous cost-spaces: applications to robotics and structural biology

Data dell'evento: 
Thursday, 19 July, 2018 - 16:00
Juan Cortés

In robotics, motion planning algorithms have traditionally aimed at finding feasible, collision-free paths for a mobile system. However, beyond feasible solutions, in many applications it is important to compute good-quality paths with respect to a given cost criterion. When a cost function is defined on the configuration space of the system, motion planning becomes a pathfinding problem in a continuous cost-space. The cost function may be related to clearance to obstacles, to energy consumption, and to many other different criteria. 

In computational structural biology, where robotics-inspirited algorithms are applied to simulate molecular motions, the cost function is usually defined by the potential energy or the free energy of the molecular system. Computing low energy paths in this context is important since they correspond to the most probable conformational transitions.
We have developed a variant of the popular RRT algorithm, called Transition-RRT (T-RRT), to compute good-quality paths in high dimensional continuous cost-spaces. The idea is to integrate a stochastic state-transition test, similarly to the Metropolis Monte Carlo method, which makes the exploration get focused on low-cost regions of the space. The algorithm involves a self-tuning mechanism that controls the difficulty of this transition test depending on the evolution of the exploration process, and which significantly contributes to the overall performance of the method. 
T-RRT is a simple and general algorithm that can take into account any type of continuous, smooth cost function defined on the configuration space. It has been successfully applied to diverse robot path-planning problems as well as structural biology problems. We have also developed several variants and improvements of the basic T-RRT algorithm to solve more efficiently particular classes of problems, and to guarantee (asymptotic) convergence to the optimal solution in an any-time fashion.
Juan Cortés received the engineering degree in control and robotics from the Universidad de Zaragoza (Spain) in 2000. In 2003, he received the Ph.D. degree in automated systems/robotics from the Institut National Polytechnique de Toulouse (France). From 2004, he is CNRS researcher at LAAS (Toulouse, France). His research interest is focused on the development of algorithms for computing and analyzing the motion of complex systems. Applications of these algorithms go beyond robotics. Indeed, he is strongly involved in interdisciplinary research in the areas of structural biology, biotechnology and materials science. Juan Cortés has participated in numerous European and French national projects in all these areas. Between 2009 and 2015, he was co-chair of the IEEE-RAS TC on Algorithms for Planning and Control of Robot Motion. He has participated in the organization of several international workshops, and he coordinates the winter schools Algorithms in Structural Bioinformatics (AlgoSB) since 2012.
Marilena Vendittelli