Distance Geometry Day in Rennes - December 7th, 2016, at IRISA, INRIA Rennes, in Les Minquiers room

[Geo-Sci-Info]

OFFICIAL WEBSITE

Distance Geometry Day in Rennes
December 7th, 2016

Distance Geometry (DG) is a consolidated research area, where mathematics and computer science are at its foundation. Classical applications of DG include the one of identifying the 3D conformations of biological molecules, the problem of localizing sensors in a given network, and the clock synchronization problem. Morever, recent research activities have been showing that there are several other applications that can be actually faced by DG. Examples are human motion adaptation, crowd simulations and virtual camera control.

This DG Day (DGD) has as main purpose to bring together researchers working on different aspects of the DG and on some of its applications. The talks will give either an overview of the current research on DG solution methods, or describe particular applications where the DG approach can bring to the discovery of new interesting scientific results.

DGD16 date and venue

The DGD16 will be held on December 7th, 2016, at IRISA, INRIA Rennes, in Les Minquiers room.

Invitation-based scientific program

9:30 - 9:50
Registration and Coffee

9:50 - 10:00
Opening, DGD16 Chair.

10:00 - 10:50
Mathematical Gems in Distance Geometry
Leo Liberti, CNRS-LIX, École Polytechnique, Palaiseau
(joint work with: C. Lavor)
Distance geometry focuses on the concept of distance rather than points and lines. Its fundamental problem asks to draw a weighted graph in a given K-dimensional Euclidean space, so that each edge is drawn as a segment with length equal to the weight, and it has applications to many fields of science and engineering (e.g. protein folding, wireless networks, robotic control, nanostructures and more). Distance geometry results are scattered throughout the whole history of mathematics starting with the Greeks. I will present some of those I find most beautiful, from a selection including: Heron's theorem, Cauchy's theorem about rigidity of convex polyhedra, Goedel's theorem about realizability on a sphere, Schoenberg's theorem linking Euclidean Distance Matrices and Positive Semidefinite Matrices, and a surprising theorem of Johnson and Lindenstrauss about approximately projecting realizations from very high dimensional spaces.

10:50 - 11:20
Practical Implementation Considerations of Interval Branch-and-Prune for Protein Structure Determination
Bradley Worley, Institut Pasteur, Paris
(joint work with: T. Malliavin, B. Bardiaux, M. Nilges, C. Lavor, L. Liberti)
The interval Branch and Prune (iBP) algorithm for obtaining solutions to the interval Discretizable Molecular Distance Geometry Problem (iDMDGP) has proven itself as a powerful method for molecular structure determination. However, substantial obstacles still must be overcome before iBP may be employed as a tractable general-purpose alternative to exist- ing structure determination algorithms. This work demonstrates how careful choice of data structures and mathematical frameworks leads to dramatic improvements in the performance of iBP in the specific case of protein structure determination. Moreover, it demonstrates how "soft" pruning of protein conformational space using interval-derived pseudo-potential energy functions may be utilized in lieu of "hard" pruning, which can become intolerant to otherwise acceptable minor geometric inconsistencies in molecular structures.

11:20 - 11:50
Feasibility Check for the Distance Geometry Problem: an Application to Molecular Conformations
Rosa Figueiredo, LIA, University of Avignon
(joint work with: A. Agra, C. Lavor, N. Maculan, A. Pereira, C. Requejo)
The distance geometry problem (DGP) consists in finding an embedding in a metric space of a given weighted undirected graph such that for each edge in the graph, the corresponding distance in the embedding belongs to a given distance interval. We discuss the relationship between the existence of a graph embedding in a Euclidean space and the existence of a graph embedding in a lattice. Different approaches, including two integer programming (IP) models and a constraint programming (CP) approach, are presented to test the feasibility of the DGP. The two IP models are improved with the inclusion of valid inequalities, and the CP approach is improved using an algorithm to perform a domain reduction. The main motivation for this work is to derive new pruning devices within branch-and-prune algorithms for instances occurring in real applications related to determination of molecular conformations, which is a particular case of the DGP. A computational study based on a set of small-sized instances from molecular conformations is reported. This study compares the running times of the different approaches to check feasibility.

11:50 - 14:00
Lunch break, light meal offered to invited speakers and scientific committee.

14:00 - 14:50
The Interplay between Graph Rigidity and Multi-Robot Coordination
Paolo Robuffo Giordano, INRIA Rennes
Graph theory has a predominant role in the field of multi-robot coordination problems (spanning, e.g., distributed formation control and estimation schemes). Indeed, graphs are a convenient (combinatorial) abstraction for representing the various sensing/communication constraints among pairs of robots in the environments. Vertexes represent robots, and edges the possibility for a robot to measure/communicate with another robot in the group.
In this context, the notion of graph rigidity is gaining popularity since rigidity of a multi-robot "framework" (i.e., formation) has proven to be a necessary condition for the solution of many formation control/cooperative localization problems. Moreover, exploiting the tools of algebraic graph theory, one can associate combinatorial graph properties, such as rigidity, to some suitable spectral properties (i.e., eigenvalues) of associated matrixes. This spectral interpretation of graph-related properties makes it possible to ultimately design simple "gradient-like" controllers for the robot group able to solve formation control and localization problems in a decentralized way.
This talk will review the concepts of graph rigidity in the context of multi-robot applications, and present some recent results obtained with a team of quadrotor UAVs (drones) used as robotics platforms.

14:50 - 15:20
Regulating Distance in Human Movement Coordination
Laurentius Meerhoff, IRISA Rennes
(joint work with: J. Pettré, R. Kulpa, A. Crétual, S. Lynch, A-H. Olivier)
The relationship between an agent (i.e., an independently decision-making entity) and its environment is the central tenet of an ecological approach to human movement. Displacement, and subsequently distance regulation, is one of the fundamental aspects of human movement. Distance needs to be regulated to avoid collision (e.g., in traffic), find a route in a complex environment (e.g., in crowd navigation) or perform coordinated behavior (e.g., in sports). In such social settings, perhaps the most prominent aspect of the environment are the other agents. Therefore, we study how collision avoidance is achieved when multiple walkers cross their trajectories. Previously it was shown that the locomotor trajectories in pairwise interactions emerge through an avoidance of risk of collision. The reciprocal interactions between these agents make the behavior complex. Moreover, many common daily life interactions encompass more than two agents, exponentially increasing the complexity. Based on animal models, it has been argued that coordination results from micro-level interactions based on simple behavioral rules which in turn lead to complex macro patterns (cf., flocking birds, schooling fish or marching on a suspension bridge). For human-to-human interactions, coordination additionally incorporates a social aspect depending on the specific situation (e.g., attractiveness of another agent). Currently, we are researching how inter-agent coordination emerges when multiple (n > 2) agents are interacting. Each agent's contribution to the inter-agent distance metrics are used to characterize the interactions. This work has implications for understanding how coordination emerges in multi-agent systems as for example crowds of people or sport teams.

15:20 - 15:50
Coffee break

15:50 - 16:30
Title to be communicated
Marc Christie, IRISA, University of Rennes 1
Abstract to be communicated.

16:30 - 17:00
Interaction-based Human Motion Analysis
Yijun Shen, Northumbria University, Newcastle
(joint work with: H.P.H. Shum, E.S.L. Ho)
Traditional methods for motion analysis consider features from individual characters. However, the contextual meaning of many motions is defined by the interaction between characters. There is little success in adapting interaction-based features in evaluating interaction difference, as they are either topologically different across interactions or high dimensional. In our work, we propose a new unified framework for motion retrieval and analysis from the interaction point of view. We adapt the Earth Mover’s Distance to optimally match interaction features of different topology, which allows us to compare different classes of interactions and discover their intrinsic semantic similarity.
We construct a comprehensive kick-boxing interaction database that is open for public for research benchmark. Experimental results show that our method outperforms existing research and aligns better with human perceived interaction similarity.

Post DGD16 publications

A special issue of Optimization Letters (OPTL, Springer) will collect short papers on the topics related to the DGD16. The special issue will be co-edited by the co-presidents of DGD16 committee. The call for papers can be downloaded here. All accepted papers will be published online individually, before print publication. The editorial system will be ready soon to accept submissions.

Previous DG events

DIMACS Workshop on Distance Geometry: Theory and Applications (DGTA16)
Rutgers University, New Jersey, USA. F. Alizadeh and L. Liberti co-Chairs. August 2016.
Many Faces of Distances (MFD14)
Campinas, São Paulo, Brazil. C. Lavor and M. Ferer co-Chairs. October 2014.
Workshop on Distance Geometry and Applications (DGA13)
Manaus, Amazonas, Brazil. N. Maculan General Chair. June 2013.

DGD16 Chair

Antonio Mucherino, IRISA/INRIA and University of Rennes 1.

DGD16 Presidents of Scientific Committee

Antonio Mucherino, IRISA/INRIA and University of Rennes 1.
Carlile Lavor, IMECC-UNICAMP, Campinas, São Paulo.

Scientific Committee

• Ludovic Hoyet, INRIA Rennes
• Davide Frey, INRIA Rennes
• Sylvain Collange, INRIA Rennes
• Jérémy Omer, INSA, Rennes
• Rosa Figueiredo, University of Avignon
• Thérèse Malliavin, Institut Pasteur, Paris
• Franck Multon, University of Rennes 2

Local organization

• Nathalie Denis, INRIA
• Antonio Mucherino, IRISA/INRIA and University of Rennes 1

A special thanks

To Mila Nobis for having designed our logo!

Fundings

The DGD16 is partially supported by CNRS (INS2I PEPS projects 2016), IRISA and INRIA Rennes.