Combinatorial search problems are ubiquitous in many fields of Computer Science. A common technique for addressing them is the exploitation of lower bounds: optimistic estimates of the cost for transforming a state into a solution. But how to compute such estimates? The proposed BARQ project addresses this question, in a highly inter-disciplinary fashion encompassing Classical Planning, Probabilistic Planning, Scheduling, and Model Checking. To our knowledge, BARQ is the first project addressing all these areas in unison. We use abstraction to obtain the lower bounds, and we use abstraction refinement to incrementally improve these bounds. Combined with upper bounding methods, this yields highly practical anytime algorithms that guarantee bounds on the quality of the current solution. The core technique we focus on is state abstraction, which imposes an equivalence relation over states. We consider a recent scheme, nested state aggregation (NSA), for constructing such abstractions. NSA incorporates a computational trick allowing fine-tuned design of the equivalence relation by selecting individual pairs of states to aggregate into one. It has been shown in Classical Planning that, in theory, this approach dominates most other known abstraction schemes. That power hinges, however, on perfect selection of the states to aggregate. Hardly anything is known about how to make this selection. BARQ fills this gap. To this end, we draw on research traditions from Probabilistic Planning and Model Checking, concerned with state abstraction and abstraction refinement. These traditions have addressed similar questions, but for very different purposes forcing the abstraction to preserve the exact set of solutions. Our research relaxes this restriction to obtain lower bounding methods instead, thus uncovering several new connections between the addressed areas. BARQ is mainly motivated by basic research questions. However, each of the four areas addressed has a tradition of practical applications, which we will leverage for the final evaluation of the developed techniques.

This research project is aimed at designing new technologies for the measure and the analysis of human motions using visual data. Recent advances in computer vision allow to capture full deformations of dynamic and evolving surfaces. In this project we propose to study how to use such capture data for the purpose of combined analyses of both shapes and motions. The interest arises in several application domains where temporal surface deformations need to be captured and analyzed. In particular, potential applications with human bodies are numerous and the project focus is therefore on human body and on how to characterize their movements through new biometric models for analysis purposes. To this aim, three main challenges need to solved. First, temporally consistent 3D models are required prior to any motion-related processing. This means that temporal correspondences, i.e. point trajectories, need to be estimated. The second challenge lies in the design of analyzing tools that consider temporally consistent 3D models. In this project, it is planned to use spectral analysis tools and manifold learning tools for that purpose. A third challenge is the application to human body analysis. This project will explore new biometric measures that account for both shapes and motions in the analysis. In order to solve for these scientific challenges, the project consortium brings together 3 academic partners from Grenoble and Nancy. The Laboratoire Jean Kuntzman participates with 2 leading research teams, PERCEPTION and EVASION, that are specializing in 3D modeling of dynamic scenes from videos and motion animation tools respectively. The GIPSA-lab and its department of Automatics provides a strong experience in human motion analysis and the ability to explore new applications in various fields including medical applications. The LORIA participates with the ALICE research team that is internationally recognized for its expertise in geometry processing and will contribute in the development of shape analyzing tools.

Developing efficient ways to represent and manipulate the three-dimensional (3D) structures of protein molecules and to calculate reliably how large proteins interact are major challenges in computational biology. Developing new algorithms which can help the experimental determination of protein structures and which can help to predict how proteins interact at a structural level could offer immense scientific and therapeutic benefits. Currently, high throughput experimental techniques can identify protein-protein interactions on a genomic scale, but it remains extremely difficult to understand how these cellular components really work at the molecular level. Hence biological scientists now need to be able to compare and analyse the 3D structures of tens of thousands of protein molecules and to calculate hundreds of thousands of protein interactions on a routine basis. We believe the best way to meet these challenges is to exploit better the special mathematical properties of the classical special functions and to extend these approaches using new developments such as the Laplace-Beltrami eigenfunctions which have recently emerged from computational geometry. Building on recent projects supported by previous ANR awards, this four-year project will bring together two teams of computational experts from INRIA Grenoble and INRIA Nancy with a group of experimental protein structure determination experts from the Jean-Pierre Ebel Institute of Structural Biology in order to develop novel algorithmic techniques for structural bioinformatics, and to apply these to current structural biology research projects. Although there are several theoretical aspects of this project, the primary aim is to develop new tools and algorithms which will be useful to many scientists working in biology, medicine, and pharmacology. However, the mathematical techniques that will be developed will be rather generic, and could be useful in many areas that require 3D object recognition and retrieval such as medical imaging, virtual drug screening, and 3D human face recognition, for example. Hence the ability to identify novel protein-protein interactions and to perform fast and accurate correlations of protein shapes and other properties could be of significant value to the pharmaceutical industry and beyond.

Unlike ordinary liquids and elastic solids, complex fluids exhibit several puzzling behaviors that critically depend on the underlying structures that compose the fluids. Indeed, many complex fluids are made of microscopic entities (such as rigid or soft particles, biological cells, macromolecules etc...) which are suspended in a liquid, and whose individual and collective behavior strongly impacts on the overall rheological properties of the fluid at the global scale and gives to complex fluids nontrivial behaviors. It is this feedback from the microscale to the macroscale that continues to pose a formidable challenge to theoretical and numerical modeling. The proposed project is oriented towards the direct numerical simulation of complex systems composed of an incompressible newtonian fluid and entities (rigid or deformable), in connection with modeling at the microscopic level (e.g. close range interaction forces will be taken into account) and at the macroscopic level (comparison with continuous, non-newtonian models). The efforts of the mathematics/numerics part of the team will be dedicated to the numerical modeling of actual experiments on vesicle suspensions carried out by the experimental part of the team, and a special attention will be paid by experimentalists to measure characteristic quantities to be compared to their computed counterparts. The numerical challenge consists in solving the incompressible Stokes and Navier Stokes equations coupled to suspended, possibly deformable, possibly many entities, in order to investigate both the microscopic phenomena and the collective behavior of such mixtures, including the case of highly concentrated suspensions. Whereas the use of existing Arbitrary Lagrangian Approach is not excluded (Stokes and Navier-Stokes solvers have been developed independently by two members of the team) to validate some test cases and investigate the behavior of inclusions close to contact, the strategies we plan to develop are mainly based on the Eulerian approach (a fixed mesh covers the domain occupied by the mixture). Beside the difficulty introduced by the deformability of the membranes which delimit the inclusions (those membranes tend to minimize a so-called bending energy whose superficial density is the square of the mean curvature), a special attention will be given to close-range interactions (lubrication forces), which are likely to play a major role in the concentrated case. Lubrication forces, which depend singularly upon inter-object distances, will be integrated in the numerical models. The expected results are (i) physical, mathematical and numerical validations of the proposed methods, (ii) their use to extract the space-time organization of the assemblies, (iii) a systematic analysis of the micro-macro coupling regarding the rheological properties, (iv) comparison of the outcome from full numerical simulations with the phenomenological equations, like Oldroyd B model; (v) a systematic confrontation of the results with the experimental findings, especially for vesicles which are known, unlike rigid particles, to have various microscopic motions. The richness of the microscopic dynamics is expected to deliver various nontrivial behaviour regarding the global rheological properties; (vi) beyond 'passive' motion of the entities, the proposed project should open new lines of inquiries towards the study of active motions (like cellular motility).