Distance Geometry Day in Rennes

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 actually be 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 are supposed to 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 was held on December 7th, 2016, at IRISA, INRIA Rennes, in Les Minquiers room.

The DGD16 was dedicated to the memory of Michel Deza, who suddenly passed away a few days before this event was held. Michel's research interests were very close to the main topic of the DGD16.

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.

The final title of this issue is "Special issue on distances in optimization and graphs dedicated to the memory of Michel Deza", and it is co-edited by Antonio Mucherino and Carlile Lavor. The special issue collects short pages (about 10 pages long).

The special issue has been published in print version on March 2020. Follow this link for additional information. The original call for papers for this special issue can still be downloaded here.

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.

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.

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.

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.

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.

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.

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.

To Mila Nobis for having designed our logo and the artwork that appeared on the back of our badges! You may want to contact directly the artist at the address nobis(dot)ma(at)gmail.com if interested in a digital copy of the artwork in high definition.