IAMOOC
A MOOC on interval analysis with applications to parameter estimation and robot localization
Luc Jaulin, Jordan Ninin, Olivier Reynet, Benoît Desrochers, ENSTA-Bretagne, UBO, Lab-STICC
lucjaulin@gmail.com
logo_lab-sticc.gif logo_intcomp.gif



Here, you have an access to the videos only. If you want to have the real IAMOOC, with the diploma, the Quiz, the forum, etc. see http://iamooc.ensta-bretagne.fr
Certified Final Exam: it will be possible to take a certified exam at the end of the school. In case of positive result, the certification can be used by students to obtain the corresponding ECTS from their PhD courses, or to comply with any other requests by their home university.

  1. Pdf with all exercises iamooc_exos.pdf
  2. Python programs corresponding to the correction (when available): iamooc_py.zip.
  3. Slides of the lesson
  4. A small doc on PyIbex and Vibes
  5. Chapter 0. Install all you need
  6. Chapter 1. Interval Computation
  7. Chapter 2. Set inversion
  8. Chapter 3. Contractors
  9. Chapter 4. Application to robot localization
  10. References
  11. List of students who got the diploma

























Chapter 0. Install all you need

Errata

In the last version of PyIbex (2017), few things have changed in the Python code and the code written in the videos is not always exactly consistent with the latest version of PyIbex. Below are listed the changes.
from pyIbex import * should be replaced by from pyibex import *
SepQInterProjF should be replaced by SepQInter
Moreover, to start Vibes from your terminal, write Vibes-viewer instead of vibes.
Some other modifications are described in the PyIbex documentation. (in magenta)



The goal of Chapter 0 is to help you to install all what you need to follow IAMOOC. You need Vibes [Dre14] for graphics.

Method

1) Install Conda as described at http://conda.pydata.org/docs/install/.
2) Install pyibex

     conda install -c benensta pyibex 
3) Install Vibes
     conda install -c benensta vibes vibes-bin 
4) Install Spyder
     conda install spyder 
A video to help you for the install is available for Windows and also for Linux (Ubuntu).

Proxy problems. In your institute, you may have a proxy which blocks some access to conda packages. In this case, the installs can be done from your home, or from any internet environment without any proxy.






Chapter 1. Interval Computation

The goal of Chapter 1 is to introduce all the mathematics related to interval analysis [Moo66]. After this chapter, you should be able to compute with uncertain numbers represented by intervals and also to approximate a set by subpavings [Jau01], i.e., union of boxes. During the practice we will implement the interval calculus under a Python environment.
What is an interval ?
Operators
Examples
Elementary functions extended to intervals
Examples
Boxes
Width
Subpavings
Inclusion functions
Monotonicity
Convergence
Natural inclusion function
Minimal inclusion function


Exercise 1. Interval arithmetic

For this exercise, you do not need to program anything, just computing with intervals. video.

Exercise 2. Intervals with Python

Using overloading operators, we show how Python allows an implementation of your own interval arithmetic library. video.





Chapter 2. Set inversion

Many problems of engineering such as parameter estimation, tuning of a controller, etc., can be cast into a set inversion problem. In this chapter, we will define the notions of set inversion and illustrate these notions on some examples. An algorithm for solving any set inversion problems will be given. This algorithm, named SIVIA (Set Inverter Via Interval Analysis), will be proposed. This algorithm will be implemented in Python and some test-cases will be solved.
What is set inversion?
Example
Inclusion tests
SIVIA
Parameter estimation


Exercise 3. Minimization of a nonconvex function

Interval analysis allows to solve non-convex global minimization problems [Kea96] without being trapped by a local minimum [Nin11]. In this exercise, a simple interval-based algorithm is implemented to illustrate the principle. video.

Exercise 4. Parameter estimation

This exercise illustrates how interval analysis can be used to solve set estimation problems [Kre97] and how it can be robustified with respect to some outliers [Jau96]. video.




Chapter 3. Contractors

A contractor [Cha09] is an operator which takes as an input a box X and contracts it into a subbox Y without removing a single solution of the problem. Contractors are necessary to solve efficiently problems containing a large number of unknowns. This chapter introduces the notion of contractor and explains how they can be implemented in Python.
Motivations
What is a contractor?
Properties
Example
Contractor for z=x+y
Contractor for primitive equations
Decomposition of complex equations
Forward-backward contractor


Exercise 5. Electric circuit

This exercise shows a very simple example related to bounded-error estimation [Poi03] which illustrates the power of interval propagation. video.

Exercise 6. Forward-backward contractor

This exercise how an interval forward-backward propagation [Ben99] makes it possible to build efficient contractors for a huge class of constraints. video.

Exercise 7. Separators

We show here how a separator [Jau14] can be built easily from two contractors: an inner and an outer. The dual nature of the separator allows us to compute an inner and an outer approximation of a set defined by several constraints. video.





Chapter 4. Application to robot localization

This chapter considers a problem of localization inside an environment with landmarks. No lessons is given in this chapter, only exercises. The main problem to be treated here is SLAM (Simulataneous Localization And Mapping). It will be decomposed into a list of 4 exercises with an increasing complexity.


Exercise 8. Contractors and separators with PyIbex

A separator is a pair of two contractors: an inner contractor and an outer contractor. This exercise illustrates how Pybex (which is a Python extension of Ibex) can be used to build easily separators for sets defined as union, intersection and complements of primitive sets. video.

Exercise 9. Estimation with PyIbex

Bounded error estimation problems can now be solved very easily and efficiently with the help of PyIbex. video.

Exercise 10. Localization of a robot [Kie99] from landmarks using range and bearing measurements

This exercise shows an important application which can be solved efficiently with interval analysis [Mei02]. Without any linearization, we show that it is possible to localize a robot in a guaranteed manner. video.

Exercise 11. Simultaneous Localization And Mapping (SLAM)

In a SLAM problem, many variables are involved with nonlinear constraints [Jau15a,Jau15b]. This problem is considered as difficult. We show here that it it possible to solve it easily and in a reliable way using intervals [Jau11]. video.
Illustration of Interval SLAM for real applications..





References


Interval analysis

[Moo66] RE Moore (1966), Interval analysis, Prentice-Hall.

[Jau01] L. Jaulin, M. Kieffer, O. Didrit and E. Walter (2001), Applied Interval Analysis with Examples in Parameter and State Estimation, Robust Control and Robotics, Springer-Verlag.


Relaxed intersection

[Jau02] L. Jaulin and E. Walter (2002). Guaranteed robust nonlinear minimax estimation. IEEE Transaction on Automatic Control. Volume 47, number 11, pages 1857, 1864. pdf.


Contractor programming

[Cha09] G. Chabert and L. Jaulin (2009), Contractor programming. Artificial Intelligence. Vol. 173, pp 1079-1100. pdf.


Global minimization

[Kea96] B. Kearfott, Rigorous Global Search: Continuous Problems (Nonconvex Optimization and Its Applications), Kluwer, 1996.

[Nin11] J. Ninin et F. Messine. A metaheuristic methodology based on the limitation of the memory of interval branch and bound algorithms. Journal of Global Optimization (2011) 50:629-644.


Robotics notions

[Jau15a] L. Jaulin, Automation for robotics, ISTE WILEY, 2015.

[Jau15b] L. Jaulin, Mobile robotics, ISTE WILEY, 2015.


Vibes

[Dre14] V. Drevelle and J. Nicola. VIBes: A Visualizer for Intervals and Boxes. Mathematics in Computer Science, 2014.


Separators

[Jau14] L. Jaulin and B. Desrochers (2014). Introduction to the Algebra of Separators with Application to Path Planning. Engineering Applications of Artificial Intelligence pdf.


Robot localization

[Mei02] D. Meizel, O. Lévêque, L. Jaulin and E. Walter (2002). Initial Localization by Set Inversion. IEEE Transactions on Robotics and Automation . Volume 18, Number 6, pages 966-971. pdf.

[Kie99] M. Kieffer, L. Jaulin, E. Walter and D. Meizel. Guaranteed mobile robot tracking using interval analysis, MISC'99 Workshop on Application of Interval Analysis to System and Control, Girona, 24-26 février 1999. pdf.


Range-Only SLAM

[Jau11] L. Jaulin (2011). Range-only SLAM with occupancy maps; A set-membership approach. IEEE-TRO. Vol 27, Issue 5. pdf.


Robust estimation with outliers

[Jau96] L. Jaulin, E. Walter and O. Didrit (1996). Guaranteed robust nonlinear parameter bounding, CESA'96 IMACS Multiconference (Symposium on Modelling, Analysis and Simulation), Lille. pdf.

[Kre97] V. Kreinovich, A.V. Lakeyev, J. Rohn, P.T. Kahl (1997). Computational complexity and feasibility of data processing and interval computations, Springer Science Business Media.

[Poi03] P Poignet, N Ramdani, O Vivas, Robust estimation of parallel robot dynamic parameters with interval analysis, CDC, 2003.


Forward-backward contractor

[Ben99] F. Benhamou, F. Goualard, L. Granvilliers, Revising hull and box consistency, Proceedings of the 1999 International Conference on Logic Programming.







List of the students who got the diploma

51 in 2015

ABADIE Moran
AUBERTOT Quentin
BARONI Kévin
BARONNIER Romain
BASSET Pierre
BEAUDOIN Maxime
BERNARDES Evandro
BOENNING Hannah
BOURGOIS Auguste
CHANU Simon
COTTEN Guillaume
DALIN Eloïse
EL ABDALAOUI Zacharie
ENNOUHI M'hamed Fadil
FONTANA Werner
GALLAND Alexandre
GY Morgan
KARKOUB El Wali
LE ROCH Gwenn
LEGAY Kevin
LI Ang
LIU Wanxin
MARTIN Pierre
MEHDI Nima
MILHEM Rémi
NEAU Guillaume
PERTIERRE DO MONTE
PLANCHOT Antoine
RAYNEAU Vincent
SOLA Yoann
SOULIE Camille
SUN Tithnara
TANGUY Florian
TERTRAIS Donatien
THIBAULT Adrien
TOMEZACH Julien
VADAINE Hugo
WELTE Anthony
ZHU Lei
ZIANE Mohamed Mahrez
BEN SAID Hela
BHIRI Bessem
BOUKALYassine
El JAWAD Alaa
MANSOUR Fatma
MESLEM Nacim
ORJUELA Rodolfo
RENAUDEAU Brice
ROUSSEAU Gauthier
TANGUY Noel
VANDERMOTTE Sylvain



33 in 2017

Raphael Abellan Romita
Alain Acevedo
Yacine Benhnini
Justine Bonnot
François Cébron
Jean-Marie CODOL
Julien Damers
Hani Dbouk
Lionel Génevé
Gabriel GODEAU
Jean-Philippe Gras
Yoann Guguen
Fabrice Lallement
Philippe Lambert
Julien Langlois
Francois Leborne
Nisha Mahato
Fatma Mansour
Mohamad Mezher
Yasmine Najar
Mohamed Outahar
Clément Rolinat
Joris Tillet
Sophie Tuton
Nicolas Veylon
Raphael Voges
Jean Walter
Mohamed Ouadrhiri
Maha Abouzai
Yves Le Palud
Emilien Fournier
Philipe Miranda de Moura
Julien Brisset