Tutorial: constraint programming for robotics

Simon Rohou, Luc Jaulin, Benoît Desrochers, Raphael Voges

8th June – 5th July

logo_ensta logo_labsticc logo_dga

logo_contredo logo_gdrmacs logo_gdrrob logo_intcomp

This tutorial is about Constraint Programming (CP), Interval Analysis (IA) and their applications to mobile robotics.

Interval analysis yields methods to compute intervals in place of real numbers, enclosing uncertainties in the mean time.
Constraint Programming aims at solving a complex problem by defining it in terms of constraints coming from the equations or the measurements.
Both concepts match perfectly for a large number of applications including Robotics, which is the subject of this tutorial proposed in the ICRA 2020 conference.

Constraint programming?

There are several ways to deal with state estimation in mobile robotics. The constraint programming approach consists in defining a problem as a set of rules and letting a solver perform the estimation. For mobile robotics, rules are constraints coming from state equations.

Efforts have been done to propose operators and solvers to apply these constraints. The goal of this tutorial is to learn how to use them and understand the efficiency of the approach on realistic robotic applications. We will see that some problems that are difficult to solve with conventional methods (Kalman filters, particle approaches) can be easily dealt with by constraint programming. This is for instance the case of poor observation measurements, time uncertainties, delays, or when the initial conditions of the system are not known.

The tutorial will stand on the Tubex library, that provides tools for computations over sets of reals and trajectories. It has been designed to deal with dynamical systems defined by non-linear differential equations and involving constraints such as trajectory evaluations, time uncertainties or delays. These computations stand on interval analysis, a well suited tool that reliably propagates uncertainties.

Requirements

Prerequisite for attending the tutorial are:

  • basic knowledge of Python or C++ (the exercises are available in both languages);

  • although the tutorial is about state estimation, you do not need skills in Kalman or particle filters.

Tubex is fully supported on Linux systems (C++ and Python3) and Windows (Python3).
We are currently working on making Tubex available for macOS (any help is welcome!). Meanwhile, we propose a Tubex-online solution: this will allow you to use Tubex in Python without having to install the library on your machine.

Contact and registration

For registration, please fill in this questionnaire:

The tutorial involves three platforms:

This tutorial is proposed to the participants of the ICRA conference. All the exercises are available on this Tubex website. The registration to the MOOC platform is not mandatory, except if you want to share with the organizers your progression and difficulties, and to obtain the diploma.

logo_youtube See the video for registration on the MOOC platform.

Diploma

To get the diploma, you need to send valid exercises to the organizers. A participant who gets a minimum total of 12 points will receive a diploma corresponding to this tutorial. This diploma can be used by students to obtain the corresponding credits for their PhD courses (equivalent to 40 hours of lessons), or to comply with any other requests from their home university.

Duration and meeting sessions

The tutorial will be held from 8th of June to 5th of July. Interactive meetings sessions are planned each Wednesday afternoon at 2PM (UTC):

  • 10th of June

  • 17th of June

  • 24th of June

  • 1rst of July

Interactive sessions (Wed. 17, June): select your slot with this form

Content of the tutorial

A list of exercises is proposed with realistic robotic applications:


Week 0: June 1 – June 7 (installation)

Before starting the tutorial, you can read some words about the concepts of Constraint Programming and Interval Analysis. This will give you a first glimpse of the philosophy of this tutorial.

To get ready, you need to install the Tubex library on your computer. Please follow the related page of the manual to see how to do it:

Then, depending on your preference between C++ or Python, you can run some Hello World! program to be sure everything is working well so far:

Note

../_images/logo_replit.png

In case you encounter difficulties to install Tubex on your computer, an alternative solution is to try Tubex online with Repl.it. You will find more information on the following page:


Week 1: June 8 – June 14

../_images/tuto_01.png
During this first week, we will install the library and perform the state estimation of a static robot between some landmarks. For the moment, we will assume that the robot does not move and is only receiving range-only data from the landmarks.
This will be an introduction to intervals, constraints and networks of contractors.
Exercise to finish: (before Monday 6th of July)
– the static range-only localization, to post on the MOOC platform.

Week 2: June 15 – June 21

../_images/tuto_02.png

We will go a step further: now the landmarks are perceived with both range and bearing data. The resolution will involve new constraints, and a decomposition will be achieved. In the second part, we will tackle the problem of indistinguishable landmarks. We still assume that we know their position, but the robot is not able to make the association between the map and the observations. The goal of this exercise is to develop our own contractor to solve this problem.

Exercise to finish: (before Monday 6th of July)
– the data association problem, to post on the MOOC platform.

Week 3: June 22 – June 28

../_images/tuto_03.png

Now, we will make the robot move and see how we can handle uncertainties on trajectories. This will be done by solving the range-only problem of Lesson B, now in a dynamical context with asynchronous measurements.

Exercise to finish: (before Monday 6th of July)
– the range-only localization, to post on the MOOC platform.

Week 4: June 29 – July 5

../_images/tuto_04.png
We will use the tubes to solve the problem Set-membership state estimation by solving data association, that is currently presented during this ICRA conference (see logo_youtube_small the video presenting the paper and the Slack channel #tua07_6).
We will end this tutorial with a range-only SLAM problem and see how Tubex can be used for online missions.
Exercise to finish: (before Monday 6th of July)
– the data association and the range-only SLAM, to post on the MOOC platform.

The following video illustrates the result of Lesson H:


Organizers and technical support

  • Julien Damers

  • Fabrice Le Bars

For any question, do not hesitate to use the MOOC platform of this tutorial, so that other participants can reply or see posted answers. We will also answer you on the Slack communication platform (#tt1) for very short questions.