Functions, Polnomials and Eigenvalues

• Authors : Jürgen Garloff
  Title : Fast and Tight Bound Functions for Multivariate Polynomials with Applications to the Reliable Analysis of Structural Frames
  Slides
  Abstract :We report on bound functions for multivariate polynomials based on the expansion of such a polynomial into Bernstein polynomials. We start with affine bound functions which are ob­tained by the least squares approximation of the whole set of control points. Then we present a method for the computation of constant bound functions which uses an implicit representa­tion of the control points so that the computational complexity becomes nearly linear w. r. t. the number of the terms in the polynomial instead of exponential w. r. t. the number of the variables (as in the traditional approach). The bound functions can be guaranteed also in the presence of data uncertainties and rounding errors. We apply the approach to the enclosure of the solution set of a system of linear equations where the coefficients of the system are ra­tional functions of parameters varying within given intervals. As an application we present examples from the analysis of structural frames, where such parametric systems appear.

• Author:Ignacio Araya, and Bertrand Neveu, and Gilles Trombettoni
  Title : Introduction of auxiliary variables into an interval function for improving its monotonicity-based image computation.
  Slides
  Abstract : The objective of this work is to better exploit the monotonicity of an interval function [f] by replacing variable occurrences in [f] with auxiliary variables. The new form of [f] can be used to compute a sharper image of the function. It can also significantly improve our new MOnotonic Hull Consistency (MoHC) filtering/contraction algorithm based on monotonicity. We improve the evaluation by monotonicity when [f] is NOT ("entirely") monotonic in [x]. The idea is to use a so-called occurrence grouping that partitions the different occurrences of x into three groups (X+, X-, Xo) such that [f] is nondecreasing in [X+] and [f] is nonincreasing in [X-]. Thanks to this occurrence grouping, [f] becomes monotonic in these new auxiliary variables (which were hidden in the initial analytic expression of [f]). To obtain a good occurrence grouping, we introduce a (monotonicity-based) estimation of the image of [f] using interval Taylor series. The problem is to find the occurrence grouping that minimizes the width of this estimation. This problem is discrete and likely NP-hard, but it becomes tractable (and no more discrete) by replacing any occurrence of x by a.X+ + b.X- + c.Xo (a, b, c are reals to determine such that a+b+c=1). This amounts in allowing the procedure to split one occurrence into three parts. We show on experiments the gain obtained by MoHC when it uses this monotonicity-based occurrence grouping procedure.

• Authors : M. Hladik, D. Daney and E. P. Tsigaridas
  Title : Bounds on eigenvalues of symmetric interval matrices
  Slides Abstract : We consider $n$-by-$n$ symmetric interval matrices, that is, a class of symmetric matrices whose entries vary inside given intervals. Their particular eigenvalues form a union of (possibly overlapping) compact intervals. Our aim is to develop methods that are cheap but produce as-sharp-as-possible bounds on the eigenvalue sets. This problem is difficult even for unsymmetric interval matrices, and the dependency caused by symmetry makes the problem much more complex. Nevertheless, symmetric matrices possess many useful properties and one can utilize diverse results developed by matrix analysts. Bounds on singular values of (square or non-square) interval matrices are obtained as a simple consequence. We present several different approaches based on Cauchy interlacing property and on a special filtering, among others, and discuss the known results as well. We compare the methods on examples and show that there is no one winner. However, a suitable combination of them leads to a surprisingly cheap and efficient procedure.

Constraint Satisfaction and Global Optimization

• Author:Yahia Lebbah
  Title : Extending a continuous constraint solver to handle mixed global optimization.
  Slides
  Abstract : This paper introduces an adaptation of constraint programming techniques and branch and bound algorithmic schema to tackle mixed integer optimization problems. This type of problems is known to be hard to manage, due to its combinatorial nature, and the difficulty to handle the continuous part. Constraint programming is now well known to be successfull in solving combinatorial discrete problems, and continuous constraints satisfaction. We have proposed in a branch and bound algorithm to tackle continuous, global and rigorous optimization problems. This framework exploits the usually known steps of branch and bound: box selection, reduction, lower-bounding, upper-bounding, and splitting. Box selection is the heuristic used to select the box between the current remaining boxes. Lower-bounding computes a rigorous lower bound of the objective function in the current box. Upper-bounding computes a feasible box. And finally, splitting is the heuristic used to choose the variables to split if the current box is still large. In this paper, we will show how to adapt simply these steps to handle mixed integer nonlinear programs, and more particularly integer variables. We have experimented this simple adaptation on the MINLPLib benchmarks. We discuss the behaviour of our implementation and we address some perspectives to exploit more deeply existing constraint programming techniques.

• Author:Ignacio Araya, and Bertrand Neveu, and Gilles Trombettoni
  Title : Monotonic Hull Consistency: A new interval constraint propagation algorithm exploiting monotonicity.
  Slides
  Abstract : It is well-known that monotonic interval functions allow a sharp image computation (evaluation). When an interval function [f], depending on a variable x (among others) is monotonic in [x], we can compute a sharper image of [f] by replacing [x] with one bound of [x]. This makes disappear, only for this variable x, the famous "dependency problem" that causes an overestimation, a widening of the image calculation when x has multiple occurrences in [f]. However, monotonicity has never been exploited in contraction algorithms for solving nonlinear constraints over the reals. We propose in this paper a new constraint propagation algorithm, called MOnotonic Hull Consistency (MoHC), that exploits monotonicity of interval functions. The propagation is standard, but the MoHC-revise procedure, used to narrow/contract the variables involved in an individual constraint, is novel. This revise procedure uses two main bricks for narrowing intervals of the variables involved in [f]. Similarly to HC4-Revise, two trees representing the analytic expression of [f] are used to perform a monotonic version of the evaluation and narrowing phases. The second brick is used to optimally narrow an interval [x] when [f] is monotonic in [x]. It performs a dichotomic process close to (while less costly than) the procedure BoxNarrow used in the Box contraction algorithm. This dichotomic process removes slices from [x] using the two trees mentioned above. An interesting result is obtained when [f] is monotonic in every interval of the variables with multiple occurrences. Indeed, the first brick of MoHC-revise ensures an optimal narrowing of the intervals of the variables occurring once in [f], while the second brick ensures an optimal narrowing of the others. Thus, in this specific case, MoHC is proven to achieve the hull consistency of the constraint. In the general case, we believe that MoHC, as opposed to HC4 and Box, is a relevant approach to handle constraints having SEVERAL variables with multiple occurrences. Experiments on standard benchmarks show the gain in performance produced by MoHC.

• Authors : Chenouard Raphael, Goldsztejn Alexandre and Jermann Christophe
  Title : Search Strategies for an Anytime Usage of the Branch and Prune Algorithm
  Slides
  Abstract : When applied to numerical CSPs, the branch and prune algorithm (BPA) computes a sharp covering of the solution set. The BPA is therefore impractical when the solution set is large, typically when it has a dimension larger than four or five which is often met in underconstrained problems. The purpose of this paper is to present a new search tree exploration strategy for BPA that hybridizes depthfirst and breadth-first searches. This search strategy allows the BPA discovering potential solutions in different areas of the search space in early stages of the exploration, hence allowing an anytime usage of the BPA. The merits of the proposed search strategy are experimentally evaluated.

• Author:Djamila Sam-Haroud
  Title : Intervals in constraint programming: some trends and open problems
  Slides
  Abstract : This talk gives a succinct presentation on interval-based techniuqes, as developped in the constraint programming community. It exposes some current trends and challenges in thos area.

Estimation

• Authors : Remei Calm, Maira García-Jaramillo, Jorge Bondia, Josep Vehí
  Title : Insulin dosage optimization based on prediction of postprandial glucose excursions under uncertain parameters and food intake.
  Slides
  Abstract : Type 1 diabetes is a metabolic disease that is accompanied by elevated plasma glucose levels comprising all forms of acute or chronic hyperglycemia, which may provoke long term microvascular and macrovascular complications. This is due to the destruction by the cells of the immune system of insulin-producing β-cells in the Islets of Langerhans in the pancreas. In the 1990s, the Diabetes Control and Complications Trial (DCCT) showed that any improvement in the glucose control as measured by the level of HbA1c leads to a reduction of the risk to suffer chronic complications associated to diabetes. For this reason, euglycemia has been established as the control objective for patients with type 1 diabetes, except if some contraindication exists. However, there still lacks a universal, efficient and safe system able to normalize the glucose levels of patients. The intensive insulin therapy required to achieve the glucose control objectives, is based on the injection of basal and bolus insulin to "emulate" its physiological secretion. The frequency and quantity of dosage depends on each single patient due to weight, physical activities, consumed carbohydrates (CH), insulin sensitivity, disease history, etc. Typically, before each meal, the patient measures preprandial blood glucose level and in relation to the planned amount of CH intake, the patient calculates the adjusted insulin dose according to some rules prescribed by the physician in the therapy plan. This therapy has as counter-action an increase in the risk of severe hypoglycemia with all their consequences if the dose is too elevated. Many systems have been developed to educate and support the patient in the insulin dosage process. The majority of these systems are intended for educational purpose and only few decision support systems have been developed. Insulin dosage advisory systems have also been incorporated in insulin pumps. This paper presents a novel method to estimate the dose and injection time relative to the mealtime required for low-risk intensive insulin therapy. The algorithm is based on an interval simulation of Hovorka glucoregulatory model. This allows considering uncertainty in the insulin hepatic and peripheral sensitivities and CH content of the planned meal. As a result, upper and lower envelopes of all the possible glucose excursions suffered by the patient are predicted, and then used to calculate the risk index of severe and mild hyper- and hypoglycemia episodes. This dosage-aid system provides the optimum insulin dosage and injection-to-mealtime with the lowest risk, according to the model. The interval simulation is resolved making use of the Modal Interval Analysis (MIA), which permits to avoid, under some conditions, the overestimate of the result. Modal interval simulation has been successfully applied in different fields.

• Author : Luc Jaulin
  Title : Probabilistic set-membership estimation.
  Slides
  Abstract : Interval constraint propagation methods have been shown to be efficient and reliable to solve difficult nonlinear bounded error estimation problems. However they are considered as unsuitable in a probabilistic context, where the approximation of a probability density function by a set cannot be accepted as reliable. This talk shows how probabilistic estimation problems can be transformed into a set estimation problem by assuming that some rare events will never happen. Since the probability of occurrence of those rare events can be computed, we can give some prior lower bounds for the probability associated to solution set of the corresponding set estimation problem. The approach will be illustrated on a parameter estimation problem and on the dynamic localization of an underwater robot.

• Author : Olivier Reynet
  Title : Estimability Characterization Using A New Interval-Based Method
  Slides
  Abstract : Estimability is the ability to estimate parameters accurately from experimental data. In this talk, we propose a new method based on interval analysis and set inversion to characterize estimability in the case of additive noise. Our approach is not another sensitivity analysis to study the influence of parameters' variation on the function's result: our method directly evaluates the error of parameter estimation from the function and an additive noise set. Besides, it does not require global identifiability. To illustrate this new method, Time Difference of Arrival (TDOA) passive location estimability is evaluated.

Global Optimization, Stability and Controller Design

• Author: Iwona Skalna
  Title : A global optimization method for solving parametric linear systems whose input data are rational functions of interval parameters
  Slides
  Abstract : An interval global optimization method combined with the Direct Method for solving parametric linear systems is used for computing a~tight enclosure for the solution set of parametric linear system whose input data are non-linear functions of interval parameters. Revised affine arithmetic is used to handle the nonlinear dependencies. The Direct Method performs the monotonicity test to speed up the convergence of the global optimization. It is shown that the monotonicity test significantly increases the convergence of the global optimization method. Some illustrative examples are solved by the discussed method; the results are compared to literature data produces by other methods.

• Author : Fabrice Le Bars
  Title : Ray tracing and stability analysis of parametric systems
  Slides
  Abstract : In my talk, I will show that ray tracing, that is commonly used in graphism, and stability analysis of an invariant linear parametric system can be considered as similar problems. I will describe a single algorithm based on interval analysis and dichotomy, that solves both problems in a fast and guaranteed way. Ray tracing (or ray casting) is based on the reconstitution of the light path from the object to the screen. It is often used to simulate pictures of a 3D scene with light effects. Objects are described by implicit functions. To know how to draw the pixels of the picture, we need to get the distance (covered by a ray) from the screen to the object's surface. For the stability analysis of an invariant linear system parameterized by p (with dim(p)=2), the delta stability plays the same role as this distance and the parameter corresponds to the pixels of the screen. I will use the Ackermann example to show the similarities between the two problems.

• Author : Sofiane Khadraoui, Micky Rakotondrabe and Philippe Lutz
  Title : Design of a robust controller for guaranteed performances: application to piezoelectric cantilevers
  Slides
  Abstract : The aim of this work is the synthesis of a robust controller, ensuring the performances, using intervals to characterize the uncertainties of the parameters model of piezoelectric cantilevers. First, one interval model [G( p)] which represents the set of piezoelectric cantilevers is derived. The interval parameters of the model include the different identified parameters of the cantilevers. To represent the wanted performances for the closed-loop, a second interval model is imposed. Finally, the controller [C( p)] is derived. This controller ensures the performances of the closed-loop for any choice in its interval parameters. The parameters midpoint of the controller [C( p)] has been taken and implemented. The experiments on the different piezoelectric cantilevers have shown the predicted performances robustness.
  Key words: Robust performances, Interval models, piezoelectric cantilevers,

• Authors : Hong Diep NGUYEN and Nathalie REVOL (LIP CNRS - ENS Lyon - INRIA - UCBL)
  Title : Relaxed method to certify the solution of a linear system
  Slides
  Abstract : We propose a relaxed method to certify the solution of a linear system Ax=b. To certify this system, we compute an enclosure of the error while simultaneously refining the floating-point solution. We proceed by adapting floating-point iterative refinement methods. To this end, the residual system is first calculated using interval arithmetic instead of floating-point arithmetic. This residual system is preconditioned by an approximate inverse of A. Then we apply an iterative method to this system, namely the interval Gauss-Seidel method, in order to improve the error bound. A problem of this method is that the use of interval arithmetic increases significantly the execution time. To tackle this problem, we introduce a relaxation technique that yields an execution time for one iteration similar to the execution time of a floating-point matrix-vector product. Although it does not avoid the precondition step, this relaxed method helps to make the interval iterative part negligible in terms of excution time, meanwhile still producing very accurate solutions, which are exact to almost the last bit when the matrix of the system is not too ill-conditioned.

Hybrid Dynamical Systems

• Authors : Andreas Eggers, Martin Fränzle and Christian Herde
  Title : SAT Modulo ODE : A Direct SAT Approach to Hybrid Systems
  Slides
  Abstract : In this talk, we present our approach to perform bounded model checking (BMC) of hybrid discrete continuous systems using constraint solving techniques. The BMC problem can be expressed by a Boolean combination of arithmetic constraints and ordinary differential equations (ODEs). While the Boolean, integer, and real-valued variables represent the state of the hybrid system, the constraint system describes traces characterized by their initial states, a transition relation connecting subsequent states by continuous flows or discrete jumps, and a target state whose reachability is to be analyzed. The reachability problem of the hybrid system therefore becomes a satisfiability problem of this type of formula. We extend our constraint solving algorithm iSAT to also handle the ODEs occuring in these formulae by using safe enclosures of the ODEs solution trajectories thereby coupling the structure of the DPLL procedure, which is used successfully in propositional satisfiability solving, with interval methods for arithmetic constraints and safe enclosure methods for the solutions of initial value problems. Our current work is focused (1) on exchanging our prototypical enclosure mechanism with Ned Nedialkov's VNODE-LP in order to obtain such enclosures more efficiently and (2) on storing once-deduced knowledge and potentially further information available on the solution trajectories persistently in the constraint system to avoid costly enclosures in the first place.

• Author : Stefan Ratschan
  Title : Interval Methods for the Analysis of Hybrid Dynamical Systems
  Slides
  Abstract : A hybrid system is a dynamical system that has both discrete and continuous state and evolution. Roughly speaking, such a system combines ordinary differential equations and finite automata, plus communication between the two. The main motivation for studying hybrid systems comes from embedded systems, where one needs to model both the discrete behavior of a computer chip and the continuous behavior of its environment. Moreover, they can also be useful for creating hybrid continuous-discrete model of plants (e.g., for modeling of gears, linearization at several points) There are two characteristics of hybrid systems that make them predestined for the usage of interval methods: In order to be able to model uncertainty and system input, hybrid systems are usually non-deterministic: They do not have a single initial state, but a whole set of initial states, and a given state is not only the source of one single trajectory but of a possibly uncountable set of trajectories. Due to the discrete behavior of hybrid systems, even two arbitrarily close states can expose totally different future behavior. Intervals methods are perfectly equipped to handle these two difficulties, since they can represent not only single states and trajectories but whole bundles of states and trajectories, and due to the ability of provably correct overapproximation. The talk will consist of a survey of interval methods for the analysis of hybrid systems with an emphasis on the author's method of verification by constraint propagation based abstraction refinement.

• Author:Nacim Ramdani (INRIA/LIRMM), Nacim Meslem (INRA)
  Title : Computing reachable sets for uncertain nonlinear monotone systems
  Slides
  Abstract : In this talk, we address nonlinear reachability computation for uncertain monotone systems, those for which flows preserve a suitable partial orderings on initial conditions. In previous works [1,2], we introduced a nonlinear hybridization approach to nonlinear continuous reachability computation : By analysing the signs of off-diagonal elements of system's Jacobian matrix, a hybrid automata can be obtained which yields component-wise bounds for the reachable sets. One shortcoming of the method is induced by the need to use whole sets for addressing mode switching. In this talk, we improve this method and show that for the broad class of monotone dynamical systems, component-wise bounds can be obtained for the reachable set in a separate manner. As a consequence, mode switching no longer needs to use whole solution sets [3]. We give examples which show the potentials of the new approach.
  [1] N.Ramdani, N.Meslem, Y.Candau, Reachability of uncertain nonlinear systems using a nonlinear hybridization. In : M. Egerstedt and B. Mishra (Eds.): HSCC 2008, LNCS 4981, pp. 415-428, 2008.
  [2] N.Ramdani, N.Meslem, Y.Candau, A hybrid bounding method for computing an over-approximation for the reachable space of uncertain nonlinear systems, IEEE Trans. Automatic Control, october 2009
  [3] N. Ramdani, N. Meslem, Y. Candau, Reachability analysis of uncertain nonlinear systems using guaranteed set integration, In Proceedings IFAC World Congress 2008, Seoul, Korea. pp.8972-8977. 2008
  

• Author: Mehdi Lhommeau
  Title : A new interval/graph approach for nonlinear control of hybdrid system
  Slides
  Abstract : In this talk we focus on the viability theory for hybrid system. A hybrid system is a dynamic system that exhibits both continuous and discrete dynamic behavior. Then, given a target contained in a constrained set and a hybrid system. We present an algorithm that provides a characterization of the capture basin of the target in the constrained set. The capture basin is defined as the subset of all feasible initial states such that there exists a control that leads the system to the target in finite time. The algorithm, also provides the controls such that the trajectory of the system reaches the target while obeying state constraints.

Continuous Dynamical Systems

• Author:Nicolas Delanoue
  Title : A new method for integrating ODE based on monotonicity.
  Slides
  Abstract : The aim of this work is to provide a new method for integrating ODE based on monotonicity of the flow with respect to initial conditions. In this talk, a comparison with existing methods (Taylor method, ...) will be given.

• Author: Philippe Mouyon
  Title : Output bounds for uncertain dynamical systems
  Slides
  Abstract :Diagnosis and supervision of dynamical systems often involve comparison of output values to thresholds. Threshold crossing shows an abnormal behaviour or a fault occurrence. However, for uncertain dynamical systems, threshold crossing may also result from the existence of an unknown, but non faulty, parameter variation. It is then important to be able to adapt threshold, taking into account for known uncertainties bounds. In my talk I will consider linear dynamical systems in continuous time, with bounded parametric uncertainties (Linear Fractional Representation of uncertain systems). The purpose of my talk is to show that it is possible to build a nonlinear dynamical system whose outputs are upper and lower bounds of the system output when it is driven by the same input as the system. And that this result stands whatever the uncertainties are within their range. Furthermore these bounds are the best possible ones as far the uncertainties may vary all over their range. The presentation uses a small set of elementary examples. It propose several solutions, that are evaluated in simulatiuon and compared. I also address the question of bounds for a cascade of uncertain systems. Finally I emphasise on some open questions: unstable systems, initial state errors, and extension to general LFR of uncertain systems.

• Authors : Sebastian Tornil-Sin, Vicenc Puig
  Title : Set Computations with Subpavings in MATLAB: the SCS Toolbox
  Slid
  Abstract : This paper presents a MATLAB Toolbox that allows to represent and manipulate subpavings, i.e unions of non-overlapped boxes. The main property of subpavings is their ability to approximate arbitrary compact sets in Rn. The functions provided in the SCS (Set Computation with Subpavings) Toolbox allows to: 1) create subpavings; 2) calculate the union and the intersection between subpavings; 3) evaluate the image of a subpaving by a function; 4) evaluate the inverse image; 5) visualize subpavings in R2. The algorithms for function evaluation (both image and inverse image), based in interval analysis tools, allows to deal with non-linear functions. The set of provided functions can be easily used for the solution of a wide spectrum of problems involving uncertainty in the automatic control. Three different examples are presented: a) the stability analysis of an uncertain system; b) the simulation of a system from an uncertain initial state; c) a parameter estimation problem in presence of uncertain measurements.

• Author : Jan Sliwka
  Title : Robust SLAM with interval analysis
  Slides
  Abstract : For a robot, the ability to localize itself in a unknown environment is essential for it to be able to move freely and perform its mission. Simultaneous Localization And Mapping (SLAM) algorithms are developed for that purpose. Those algorithms use robot sensor measurements (telemeter, compass,...) and return the map of the area and the actual position of the robot. The complexity of those algorithms lies in the fact that first, the equations related to this problem are non linear, so the methods that linearize the equations like the Kalman filter based methods will have some trouble solving it. In the other hand, the aforementioned measurements will contain outliers. In the case of ultrasonic telemeters, an outlier may be caused by some unpredictable objects between the robot and the target or by the echo caused by the multiple path of the ultrasonic wave. Least square methods are not adapted to that kind of data. In the talk, I will explain how a SLAM problem can be translated into a Constraint Satisfaction Problem (CSP) i.e. a set of equations. The obtained CSP is solvable using set membership theory methods. The map of the environment can often be represented by a set of polygons and standalone segments so we chose an example where we try to make SLAM in a triangular room using telemetric measures.

• Authors : M. Delafosse, L. Delahoche, B. Marhic, A.Jolly-Desodt
  Title : An interval SLAM paradigm based on stereoscopic bearing measurement
  Abstract : SLAM (Simultaneous Localization And Mapping) is a state estimation process of the robot localisation of and the localisation of surrounding objects to build both the environment map and the navigation trajectory. This problem was studied with different formalisms and different supports. The first is a topological environment representation with a graph of the significant areas in the environment. The second is metric approach that consists in estimating the robot's state and the landmarks. The third is a grid based method that computes the occupancy probabilities of the robot and landmarks in a map built with a set of cells. In the last two representations some probabilistic formalisms are either based on Kalman filtering, EKF-SLAM [5], or are based on Particle Filtering [2]. Other solutions used the theory of evidence with an occupancy grid model [3]. We obtain some interesting results with this last approach. Luc Jaulin proposes a set alternative. The SLAM problem is treated like a constraint satisfaction problem (CSP) that needs to be solved [4]. Indeed, the state computing of the robot localisation allows the state estimation of the beacons and landmarks, and vice versa. Therefore the constraints are deduced logically. In our previous works [1], we have noted the interest of constraints propagation in a localisation solution. In this study we extend our localization paradigm to propose a SLAM paradigm. It consists in coupling an interval state process with an evidential architecture to achieve a robust tracking of the object and we have obtained a reliable trajectory.
  [1]A. Clerentin, M. Delafosse, L. Delahoche, B. Marhic ,AM. Jolly - Uncertainty and imprecision modeling for the mobile robot localization problem Autonomous Robots Volume 24 Number 3 avril 2008
  [2]G. Grisetti, C. Stachniss, W. Burgard, "Improved Techniques for Grid Mapping With Rao-Blackwellized Particle Filters", IEEE Transactions on Robotics 23(1): 34-46 (2007).
  [3]Delafosse M., Delahoche L., Clerentin A., Ricquebourg V., Jolly-Desodt A.M. - "A Dempster-Shafer fusion architecture for the incremental mapping paradigm" Fusion 2007, The 10th International Conference on Information Fusion - July 9-12 2007 - Quebec City, Canada
  [4]Luc Jaulin, Gilles Chabert , "Interval and Boolean constraint propagation for simultaneous localization and map building", SWIM 08, Small Workshop on Interval Methods, Montpellier, France, 19-20 June 2008
  [5]Tim Bailey and Hugh Durrant-Whyte, "Simultaneous Localisation and Mapping (SLAM): Part I The Essential Algorithms. ", IEEE Robotics and Automation Magazine, June 2006,
  

• Author : Gilles Chabert.
  Title : A Constraint on the Number of Distinct Vectors with Application to Localization.
  Slides
  Abstract: In this talk, we will describe a generalization of the "nvalue" constraint that bounds the number of distinct values taken by a set of variables.The generalized constraint (called "nvector") bounds the number of distinct (multi-dimensional) vectors. We will show that this global constraint has a significant role to play in many problems where a limitation on the number of resources is known, by taking the example of beacons in the simultaneous localization and map building problem (SLAM). This problem arises in the context of mobile robotics. We will show that enforcing hull consistency on this type constraint is NP-complete. A simple contractor will be proposed and tested on a realistic example.

• Authors : Vincent Drevelle, Philippe Bonnifait (UTC)
  Title : On the use of robust set inversion to characterize GNSS protection levels
  Slides
  Abstract : Global Navigation Satellite Systems (GNSS) are commonly used for any positioning service. In a safety aware context, a punctual estimate of the user location is not usable without confidence indicators. Protection levels are now the usual scheme to characterize this confidence. They are defined as bounds of the estimated user position error, given an integrity risk. Classical methods rely usually on iterative robust least squares able to handle an outlier at a time. In this work, we present a new bounded-error approach that enables to compute a location zone from raw GPS pseudo-range measurements, given a chosen integrity risk. Bounds are set on measurements to meet the specified risk requirements, and then a set-inversion is performed to compute the user location zone. Using guaranteed set-inversion algorithms, the integrity risk of the true position no being inside the computed zone is bounded by the risk taken when setting bounds on measurements. To deal with multipath measurements in urban areas, robustness to outliers is achieved by using a relaxed set inverter. Data redundancy, needed to keep the location area narrow, can be increased by fusing altitude information stored in a digital elevation model. Experimental results with real GPS data are presented. They prove that set-membership methods are very efficient and less pessimistic than we thought before carrying out this study.

• Authors : Sébastien Lengagne (LIRMM), Nacim Ramdani (INRIA/LIRMM), Philippe Fraisse (LIRMM)
  Title : Planning and Fast Re-Planning of Safe Motions for Humanoid Robots using interval analysis.
  Slides
  Video 1 | Video 2
  Abstract : Motion databasing is an important topic in robotics research. Humanoid robots have a large number of degrees of freedom and their motions have to satisfy a set of constraints (balance, maximal joint torque velocity and angle values). Thus motion planning cannot efficiently be done online. The computation of optimal motions is performed offline to create databases that transform the problem of large computation time into a problem of large memory space. In fact, thanks to a parametrization of the joint value, motion planning can be seen as a Semi-Infinite Programming problem (SIP) since it involves a finite number of variables over an infinite set of constraints. Most methods solve the SIP problem by transforming it into a finite programming one using a discretization over a prescribed grid. We show that this approach is risky because it can lead to motions which may violate one or several constraints. Then we introduce our new method for planning safe motions. It uses Interval Analysis techniques in order to achieve a safe discretization of the constraints. We show how to implement this method and use it with state-of-the-art constrained optimization packages. We illustrate the capabilities of our method for planning safe motions for the HOAP-3 humanoid robot. In a second step, we address the case where HOAP-3 plays soccer. In such a case, the kicking motion is usually a benchmark motion that is computed off-line, and thus without taking into account the current position of the robot, the ball or the direction of the goal. Moreover, robots must react quickly to any situation, even if not expected, and cannot spend time to generate a new optimal motion by the classical way. Therefore, we propose a new method for fast motion re-planning based on an off-line computation of the feasible set of motion parameters, using Interval Analysis.