Workshop "set computation for control" in Brest
Topic: Intervals and geometry

Groupe de travail MEA (méthodes ensemblistes pour l’automatique)

The next weeting of our group GT MEA will take place Thursday, december 5, 2013 at l'ENSTA Bretagne, Room F203.

In case of problem when you arrive, phone Luc Jaulin : 06 82 99 00 41.

The presentations will be in French. Now, since the slides are downloaded from anywhere in the world, please, please, write your abstract and your slides in English.

To register (important to be allowed to enter the school), please, send us before Friday (if possible) your name, your lab/company to luc.jaulin@ensta-bretagne.fr, annick.billon-coat@ensta-bretagne.fr, jordan.ninin@ensta-bretagne.fr

How to come?

Program

9h30 Welcome and Coffee

10h-10h30

Speaker. Luc Jaulin, LabSTICC, IHSEV, ENSTA Bretagne, OSM, Brest.

Title. Separators: a new interval tool to bracket solution sets; application to path planning. Slides.

Abstract. Contractor algebra is a numerical tool based on interval analysis which makes it possible to solve many nonlinear problems arising in control, such as identification, path planning or robust control. More precisely, contractor-based techniques combined with a paver can provide inner and outer approximations (with subpavings) of solution sets. To compute the inner subpaving, the De Morgan rules has be used to express the complementary set of the solution set. The task is not so easy and has never been made automatic, to our knowledge. This talk presents the new notion of separators which is a pair of complementary contractors and presents the corresponding algebra. Using the separator algebra inside a paver will allow us to get an inner and an outer approximation of the solution set in a much simpler way than using any other interval approach. Some test cases related to simple geometrical problems (such as Path Planning) will be provided to illustrate the efficiency of the approach.

10h30-11h00

Authors. Rémy Guyonneau, Sébastien Lagrange and Laurent Hardouin. Université d'Angers, Angers, France.

Title. Visibility Contactors; Application to mobile robot localization. Slides.

Abstract. Visibility is studied and used in several fields: computer graphics, telecommunication, robotics... For instance, in Computer-aided design (CAD) synthesis images are created by simulating light propagation in a scene. Visibility notions are then necessary to compute the visible objects from a point of view, and the shadow of those objects. In mobile robotics the visibility is used for path planning (visibility graph) and localization problems. This presentation is about visibility information for mobile robot localization. The objective is twofold. First a visibility notion based on segment intersections is presented. By considering a set-membership approach it is possible to develop contractors associated to this visibility relation. Then two applications of those visibility contractors to mobile robot localization are presented. The first one corresponds to the pose tracking of a team of robots. The idea is to use a Boolean information (the visibility between two robots: two robots are visible or not) in order to avoid the drifting of those robots (in order to maintain the precision of their position estimations). The second application corresponds to the processing of an original constraint for a set-membership global localization algorithm. This global localization algorithm is based on a CSP approach (Constraint Satisfaction Problem). Adding a visibility constraint to this CSP improves the accuracy of the algorithm.

11h00-11h30

Speaker. Ignacio Salas. Ecole des Mines de Nantes.

Title. A contractor approach to solve the packing problem. Slides.

Abstract. The packing problem can be stated as finding the position of some objects that respect the non-overlapping constraint. In our work, we are considering objects described by conjunctions of non-linear inequalities, and more generally, disjunction of conjunctions to allow piece-wise definition of objects. Note that there is no assumption of convexity. We only assume connexity. In this problem, the variables of the problem are the coordinates of the origin of each object. Our main contribution is the construction of a contractor, that is, an operator that reduces the domains of objects origin. This contractor can be used by any solver. In our experiments, we have tested it with a classical branch and bound algorithm. Our contractor is based on the more elementary non-overlapping constraint relating only two objects, one being considered as a variable (and called the “moving” object), the other being temporarily considered as a constant (and called the "reference" object). We have developed two complementary techniques: the first one creates a forbidden box for the moving object inside its domain, that is, a box that only contains points that violate the constraint. Forbidden boxes obtained with different reference objects can then be combined in a sweeping loop algorithm, resulting in a contraction for the moving object. The second technique contracts the domain of the moving object to a subbox that encloses the boundary of the feasible space with respect to the elementary non-overlapping constraint. Using connexity, we can then easily derive a contractor. Both techniques result in elementary contractors that can be propagated in a fixpoint loop, each object being considered in turn as "moving" and the others as "references". In this talk, we will detail both techniques and give our first experimental results.

11h30-12h00

Speaker. Frédéric Messine (Université de Toulouse). Slides.

Title. Quelques histoires sur les petits octogones optimaux et leurs preuves assistées par ordinateur.

Abstract. Nous verrons dans cet exposé comment des problèmes de géométrie plane, ouverts pour la plupart depuis 1922, peuvent être résolus à l'aide d'un ordinateur et de codes déterministes d'optimisation globale. En effet, dans la famille des petits polygones convexes ("petits" dans le sens où la distance maximale entre 2 sommets est 1), on peut se poser la question suivante : Les petits polygones réguliers sont-ils de périmètre maximal, de surface maximale ou de largeur maximale ? En fait, l'intuition nous trompe et nous ferait dire oui ! Cependant, il n'en est rien dès lors que le nombre de sommets est pair. Nous présenterons donc une petite famille particulière de petits octogones optimaux et nous montrerons comment certifier ces solutions numériques à epsilon près (en utilisant entre autre un code d'optimisation globale basée sur l'arithmétique d'intervalles).

12h00-14h00. Lunch (free).

14h00-14h30

Speaker. Gilles Chabert LINA, Nantes

Titre. Construire son propre contracteur avec Ibex: un exemple géométrique. Slides.

Abstract. Dans cet exposé, nous montrerons comment intégrer un contracteur spécifique dans Ibex et le combiner avec ceux fournis par défaut

 dans la librairie. Nous prendrons comme exemple l'intersection de deux cercles c1 et c2 dans le plan. Plutôt que de mettre en séquence des algorithmes de contraction de type forward-backward ou Newton intervalle sur les équations du cercle, il est possible de donner une formule explicite pour les deux points d'intersection. Cependant, celle-ci nécessite de prendre en compte les différentes valeurs possible du signe d'un discriminant. Il est donc plus commode

 d'écrire directement un algorithme et de voir la relation x=inter(c1,c2) comme un contracteur dédié.

 Nous montrerons comment écrire ce contracteur et le combiner avec les contracteurs existants, en illustrant cela sur une petite application en robotique mobile. Le robot considéré évoluera selon une dynamique très simple et sera muni d'un télémètre lui permettant d'obtenir des équations de distance avec des obstacles connus. Ces équations de distance, prises par paires, pourront alors être contractées de façon optimale grâce à l'algorithme ci-dessus.

14h30-15h00

Speaker. Antonio Mucherino, IRISA, Rennes.

Title. Molecular Distance Geometry and Atomic Orderings. Slides.

Abstract. The Molecular Distance Geometry Problem (MDGP) is the problem of finding the conformation of a molecule by exploiting available distances between some pairs of its atoms. The MDGP is NP-hard. In its basic form, it is a constraint satisfaction problem, that is usually reformulated as a global optimization problem having a continuous space as a domain. Since some years, we are working on a class of MDGP instances for which the search space can be discretized, and on a branch-and-prune (BP) algorithm that is potentially able to enumerate the entire solution set of such instances. The discretization is possible when certain assumptions, strongly based on the ordering in which the atoms of the molecule are considered, are satisfied. Recent advances in discovering discretization orders for the atoms of well-known molecules such as proteins will be presented.

15h00-15h30

Speaker. Stéphane Le Menec (MBDA, Le Plessis-Robinson)

Title. Collision Avoidance Based on Differential Games. Slides.

Abstract: Collision avoidance of moving objects is a crucial feature for autonomous flying vehicles such as drones and missiles. Validation of collision avoidance capabilities is mandatory when dealing with applications involving several platforms. Plenty of missions: satellite formation flying; cooperative search and rescue; air traffic control (civil aircrafts) and raids of cruise missiles require to master the sense and avoid aspects for safety purpose. The autonomous collision avoidance process on which we focus on is based on a standalone decision making process and on-board sensors only. There exist powerful collision avoidance mechanisms which rely on synchronized supervised manoeuvres between cooperative moving vehicles. The centralized collision avoidance requires external additional inputs provided through data links. However, for robustness reasons, we apply protocols based on unsafe state sets which are capture zones of two player non-cooperative differential games. These unsafe sets are backward reachable sets computed off line using interval analysis algorithms. This study is part of VIATIC project (Viability and Autonomy of Systems in Unreliable and Constrained Environment) with funding support of ANR (French National Research Agency).

15h30-16h00

Speaker. Jérémy Nicola and Vincent Drevelle

Title. VIBes: a Visualizer for Intervals and Boxes. Slides.