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.
After the news of Michel's passing away, we have decided to change the dedication of our special issue of
Optimization Letters (OPTL, Springer).
While keeping collecting contributions from DGD16 invited speakers and participants, we have invited
all collegues close to Michel to contribute to this special issue.
DGD16 scientific program (invitation-based)
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.
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
15:50 - 16:30
Towards New Models for Virtual Cinematography
Marc Christie, IRISA, University of Rennes 1
(joint work with: H-Y Wu, Ch. Lino, Q. Galvane)
Virtual cinematography is the application of real cinematography techniques (how to stage the scene, place cameras, place lights, and switch between cameras) into virtual 3D environments. The problem is classically expressed as an optimization problem searching for camera, stage and light parameters that ensure "best cinematography", i.e. the respect of key rules and conventions found in the film literature. However, expressing visual cinematographic rules is a challenging problem, and the optimization remains too computationally complex to be solved in times compatible with user interaction. Our approach therefore consists in designing alternate representations with reduced dimensions, and in which cinematographic rules are easier to express and easier to solve. We'll present our current results, and open a discussion on how to generalize these approaches and possibly link them with distance geometry topics.
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.
Previous DG events
DGD16 Presidents of Scientific Committee
Antonio Mucherino, IRISA/INRIA and University of Rennes 1.
Carlile Lavor, IMECC-UNICAMP, Campinas, São Paulo.
Antonio Mucherino, IRISA/INRIA and University of Rennes 1.
The DGD16 is partially supported by CNRS (INS2I PEPS projects 2016), IRISA and INRIA Rennes.