HSCC 2018 Sources

Overview

This page contains all information for repeating the numerical results from the paper “Improving validated computation of Viability Kernels”, Benjamin Martin and Olivier Mullier, submitted to HSCC 2018. In particular, the computed figures and CPU timings (which might be different depending on your computer) of Section 4.

The method we have developed is an improved version of the two phase method from Monnet et al. [1]

The codes are in C++ and are based on the interval analysis library Ibex. We also use DynIbex for validated numerical integration.

We provide two ways for running the different programs: sources files that requires to be compiled on your own or a virtual machine image for Virtual Box, using the Lubuntu linux distribution, where everything is already set up and ready to work. Note that our programs have been implemented in Linux (Ubuntu), and NOT tested on Windows nor MacOS.

The programs are in LGPL, and have been produced thanks to the DGA/MRIS project “Sureté de Fonctionnement des Systèmes Robotiques Complexes”, Ecole Polytechnique and ENSTA Paristech.

Why two separated programs for the first and second phase ?

The two programs given here were originally two different projects from the two authors. We remarked that we could bring some improvements to the method from Monnet et al. [1] and started to work together for this purpose.

The algorithm used in the first phase is part of a more general framework for validated static analysis of non-linear dynamical systems. It is based on the latests versions of Ibex. The algorithm for the second phase is a framework of the method from Monnet et al. [1] based on DynIbex, currently available only for older versions of Ibex. Unfortunately, those two versions of Ibex are not compatible, and the two different programs could not be efficiently merged together.

This makes the usage a bit cumbersome, but we provide the sources packages with several scripts in order to ease the installation process.

Downloads

We propose two ways of running the experiment: either download the source archive that you need to compile yourself or download the virtual machine archive for virtual box, on which everything is ready for running.

Requirements

The program for the first phase require the Ibex library version 2.4.1, already in the archive. A more recent version of the library might work (although not tested), so if you want to use your own installed version, you might just skip its installation.
The program for the second phase requires DynIbex, also contained in the archive. Note that this is an “ongoing work” version of the library which is different from the one available on the official webpage. Use the version that is provided in the archive.

Ibex requires several applications in order to be installed (here for more information):

  • g++
  • gcc
  • flex
  • bison
  • python2.x
  • make
  • pkg-config

Additionally for the program ViakKer, we require:

  • cmake
  • gnuplot (for drawing pictures)

In order to use the virtual machine, download a version of VirtualBox that best fits your system.

Instructions

Compilation of the sources from the archive

Uncompress the archive wherever you want on your system. It will create a folder HSCC_VIAB containing three folders and three scripts:

  • 3rd contains the installations of Ibex 2.4.1 and DynIbex.
  • viab_init contains the sources of the improved first phase of the algorithm.
  • ViabKer contains the sources of the improvement method and of the original ellipsoidal methods used by Monnet et al. [1]
  • run_numeric_experiment.sh is a script for running automatically all the numerical experiment of our paper.
  • clear.sh is a script for erasing EVERYTHING that has been produced by the experiments, including the final resulting figures. It is not necessary to call this script.
  • instal.sh is a script which compiles and install locally the provided Ibex and DynIbex versions and the two programs viab_init and ViabKer.

The script install.sh is set up so that external libraries will be installed locally in HSCC_VIAB.

Compiling everything then just requires to call this script from the HSCC_VIAB folder:

$ cd HSCC_VIAB

$ sh install.sh

Note

You can comment the first lines of the script install.sh for the installation of Ibex 2.4.1 if you already have a more recent version of Ibex installed on your computer. But we recommend to use the version provided in the archive.

Use of the Virtual Machine

Once VirtualBox is installed and our virtual machine image downloaded, open VirtualBox and go to “File->Import Appliance” and select the .ova file for importing the virtual machine. Then run the virtual machine.

The virtual machine guest system runs on Lubuntu and shall logged in automatically. If not, or a the password is required somehow, the login and password of the VM are:

login: hscc

password: hscc2018

In the virtual machine

To open a terminal, go to the bottom left “getting started” button and “System Tools -> LXTerminal”. All the programs are installed in the home directory in the folder HSCC_VIAB. It follows the same structure as in the provided archive (see above). For going there from the terminal, simply run:

$ cd HSCC_VIAB

Since everything is already compiled and installed, there is no need in calling the install.sh script.

Running the experiments

In order to run the experiments, just type the following command in the terminal from the HSCC_VIAB directory:

$ sh run_numeric_experiment.sh

It can take a bit of time for the experiment to finish. The CPU times for treating each instance are given on the standard output, with timings for both phases of the algorithm and the summed total timings. You may want to redirect the standard output for storing the results in a file.

You will see several new folders and files that are created as the script goes. They are used to store temporary data with the exception of the folder figures which contains all the figures representing the computed paving of the inner-approximation of the viability kernel.

Note

The two programs viab_init and ViabKer communicates through a file storing the parameters of the computed barrier functions.

Getting the results

Once the script run_numeric_experiment.sh has finished, you will find in the folder figures all figures representing the paving of the inner-approximation after each iteration of the improvement phase (including the initial one). The different sub-folders of figures are:

  • COTH_default Car On The Hill example using the default first phase
  • COTH_ViabInit Car On The Hill example using the improved first phase
  • COTHOUT_ViabInit Car On The Hill example with non-convex safe set using the improved first phase
  • ROD_ViabInit Balancing Rod example (or inverse pendulum) using the improved first phase

 

 

[1] Dominique Monnet, Luc Jaulin, Jordan Ninin, Alexandre Chapoutot, and Julien Alexandre-dit Sandretto. Viability kernel computation based on interval methods. In SWIM (Summer Workshop on Interval Analysis), 2015.