SWIM'09
Small Workshop on Interval Methods
June 10-11, 2009
Ecole Polytechnique Fédérale de Lausanne
Description - Call for talks - Dates - Registration, format & proceedings - Organisation - Accomodation and travel - Slides
The goal of this workshop is to bring together researchers and practitioners working on interval methods and their applications, providing a forum to review and discuss the state-of-the-art in this area and fostering cross-fertilization between different approaches.
The SWIM'09 workshop is intended to build on the success of the first edition, held in Montpellier, which was initiated by the french working group MEA ("Méthodes ensemblistes pour l'automatique" or "Set Membership methods for automatic control" : www.lirmm.fr/ensemble).
Twenty one speakers from several countries (Poland, Brazil, Bulgaria, Spain, Canada, Switzerland, Pakistan and France) attended SWIM'08, where they discussed their most recent ideas and developments and thought together about the most promising new directions.
If you want to present a talk, please send an one page abstract via email to one of the organizers, no later than May 1st, 2009.
If you simply plan to attend the workshop, please send an email to one of the organizers.
SWIM'09 presentations will take place in the INR219 room at the Intelligence artificial Laboratory (LIA,EPFL))
Accommodation : an extensive list of Lausanne's hotels is available at http://www.lausanne-tourisme.ch/LT/Accomodation/_S_63358
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 obtained 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 representation 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 rational 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.
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.
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: 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 : 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 : 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.
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.
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.