Search

This article proposes a new set-membership method for estimating the trajectories of dynamical systems, when the states are completely unknown and only nonlinear observations are available. The first part of the proposed method is symbolic and follows the decomposition of Brunovsky, i.e., it decomposes the set of differential equations describing the dynamical system into two blocks of constraints: one block gathers nonlinear analytical equations that do not involve differential operators, while the other block is composed of linear chains of integrators. The second part of the method, which relies on the symbolic decomposition, is numerical and based on a contractor approach. It involves a specific optimal operator for narrowing the sets of feasible solutions. This approach is shown to be efficient on a difficult problem of dynamic localization of a mobile robot, without any prior knowledge about its states.

Set-based state estimation procedures have the advantage of enclosing all possible system states under the assumption of bounded measurement uncertainty, the structural correctness of dynamic systems models, and the representation of external disturbances and imperfectly known parameters by finitely large sets. In contrast to stochastic counterparts, often employing one of the available variants of Kalman filters, set-based approaches are less widely used. The reason for this observation is the fact that naive implementations often suffer from a non-negligible degree of overestimation and that (unless certain monotonicity properties are satisfied) set-based computations come with a notable increase of the computational complexity, resulting among others from required interval splitting procedures. This paper tries to resolve both issues by means of an ellipsoidal implementation of a discrete-time set-valued state estimation procedure that is validated experimentally and compared with an Unscented Kalman Filter (UKF) for a laboratory-scale magnetic levitation system.

A wide variety of approaches for set-valued simulation, parameter identification, state estimation as well as reachability, observability and stability analysis for nonlinear discrete-time systems involve the propagation of ellipsoids via nonlinear functions. It is well known that the corresponding image sets usually possess a complex shape and may even be nonconvex despite the convexity of the input data. For that reason, domain splitting procedures are often employed which help to reduce the phenomenon of overestimation that can be traced back to the well-known dependency and wrapping effects of interval analysis. In this paper, we propose a simple, yet efficient scheme for simultaneously determining outer and inner ellipsoidal range enclosures of the solution for the evaluation of multi-dimensional functions if the input domains are themselves described by ellipsoids. The Hausdorff distance between the computed enclosure and the exact solution set reduces at least linearly when decreasing the size of the input domains. In addition to algebraic function evaluations, the proposed technique is—for the first time, to our knowledge—employed for quantifying worst-case errors when extended Kalman filter-like, linearization-based techniques are used for forecasting confidence ellipsoids in a stochastic setting.

Simulating dynamic systems with bounded uncertainty in initial conditions and selected parameters is a common task for the reliability analysis of closed-loop control structures as well as for a simulation-based parameter identification on the basis of uncertain measurements. However, dealing with bounded uncertainty is not a trivial task. On the one hand, the naive application of interval analysis often leads to excessively large bounds which may yield state enclosures that are by far too pessimistic to be useful in practice. On the other hand, the use of grid-based or probabilistic and Monte-Carlo like simulation approaches suffers from the disadvantage that they do not provide a guarantee of the correctness of the obtained solutions. Using insufficiently many or badly chosen samples may lead to the phenomenon that critical system states are not detected so that the computed results underestimate the range of reachable states. Therefore, a novel ellipsoidal state enclosure technique is presented which does not require the online solution of linear matrix inequalities (LMIs). It uses the newly introduced representation of state domains by means of thick ellipsoids. These domains simultaneously represent inner and outer enclosures of the reachable states and directly provide a measure for the tightness of the obtained results, regardless of whether the system is linear or nonlinear or whether it is stable or not.

In this paper, we propose a new approach to compute the projection of a set defined by polynomial equations. It assumes that the polynomial equations have some nice symmetries and that a solution of the projection problem is already available in the case where the variables along which we project are all positive. A new interval-based algorithm which combines symmetry operators and set quotient is proposed. Symmetries are used to move from one part of the space to another. The set quotient is needed to avoid redundant symmetries. The projection procedure yields an inner and an outer approximations of the projected set. Two applications are considered. The first one corresponds to the characterization of the space occupied by a rotating polygon, and the second one deals with the estimation of the speed of a moving object observed by several robots with uncertain orientations. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of reaching and keeping a target position for a sailboat. A method to control sail angle is proposed, using an adaptive adjustment of the sail to regulate the acceleration of the sailboat. A tacking strategy is defined to navigate into the wind, arrive upwind to slow down the boat and then to stay close to the target point. Simulation results show the effectiveness of the proposed approach. The stability of the sailboat using the proposed control has been proven.

This paper proposes an original interval-based method to compute an outer approximation of all invariant sets (such as limit cycles) of a continuous-time nonlinear dynamic system, which are included inside a prior set of the state space. Contrary to all other existing approaches, our method has the following properties: first, it is guaranteed (a solution cannot be lost); second, it is applicable to a large class of systems without any specific assumption such as the knowledge of a Lyapunov function or any partial linearity; and third, there is no need to integrate the system. [ABSTRACT FROM AUTHOR]

This paper deals with the set inversion problem X = f-1(Y) in the case where f: Rn→ Rmdepends on a parameter vector p ∈ Rqwhich is known to be inside a box [p]. We show that for a large class of problems, we can obtain an accurate approximation of the solution set, without bisecting in the p-space. To do this, symbolic methods are required to cast our initial problem into a chain of set-inversion problems, the links of which have some nice properties with respect to p. As an application, we consider the problem of computing the set of all initial states of an uncertain discrete-time state system that reach a target set Y in a given time.

This technical note deals with the guaranteed characterization of the part of the space that has been explored by a robot. The main difficulty of the problem is to take into account the uncertainty associated with the trajectory and the fact that the dimension of the visible space at time $t$ may be smaller than that of the workspace. An example involving an experiment made with an actual underwater robot is presented in order to illustrate the efficiency of the approach. [ABSTRACT FROM PUBLISHER]

Many methods exist to detect stable equilibrium points x ∗ of nonlinear dynamical systems x ̇ = f ( x ) . Most of them also prove the existence of a neighborhood N of x ∗ such that all trajectories initialized in N converge to x ∗ . This paper provides a numerical method combining Lyapunov theory with interval analysis which makes to find a set N which is included in the attraction domain of x ∗ . [ABSTRACT FROM AUTHOR]

This paper proposes an interval based approach for localizing a group of underwater robots with unsynchronized clocks. We use sonar communication and consider that the travel time of the sonar waves cannot be neglected, e.g. when the robots are fast and far-spaced. Therefore we cannot suppose that we measure a true distance between robots at the same time, but between robots at di􀉼erent times. Moreover, as the clocks of the robots are unsynchronized, the emitting and receiving times of the sonar waves are uncertain. To solve this problem, we cast the state equations of our robots as a constraint satisfaction problem and consider the sonar measurements as intertemporal constraints on uncertain times. We introduce the notion of interval of function to encompass the robots trajectory and clock with their uncertainty. We then use interval propagation to successively contract these intervals around the true position and clock of the robots. Several test cases are provided, with both simulated and experimental results.

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 paper 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.

Abstract In this paper, a new algorithm based on Set Inversion techniques and Modal Interval Analysis is presented. This algorithm allows one to solve problems involving quantified constraints over the reals through the characterization of their solution sets. The presented methodology can be applied to a wide range of problems involving uncertain (non)linear systems. Finally, an advanced application is solved.

Abstract In this paper, we show that the problem of computing the smallest interval submatrix of a given interval matrix [A] which contains all symmetric positive semi-definite (PSD) matrices of [A], is a linear matrix inequality (LMI) problem, a convex optimization problem over the cone of positive semidefinite matrices, that can be solved in polynomial time. From a constraint viewpoint, this problem corresponds to projecting the global constraint PSD (A) over its domain [A]. Projecting such a global constraint, in a constraint propagation process, makes it possible to avoid the decomposition of the PSD constraint into primitive constraints and thus increases the efficiency and the accuracy of the resolution.

This paper proposes a new approach to solve the problem of finding a control sequence for a nonlinear discrete-time system that should satisfy given set-membership specifications on the state and the output vectors. This approach is based on set computation and constraint propagation. Two illustrative examples are provided. The approach is then extended to deal with the robust control problem of nonlinear discrete-time systems.

In a bounded-error context, reliable set-inversion algorithms such as SIVIA provide guaranteed estimates of the set of all the parameters deemed compatible with the selected model and the collected data. assuming that all the uncertain variables of the model are those to be estimated. In this paper we propose a new approach to estimate the parameters of interest assuming that there are other parameters that will not be estimated. This leads to the idea of set projection. A new algorithm for set projection is proposed and applied to the estimation of thermal quantities via a new experimental device to be calibrated.

The problem considered here is state estimation in the presence of unknown but bounded state perturbations and measurement noise. In this context, most available results are for linear models, and the purpose of the present paper is to deal with the non‐linear case. Based on interval analysis and the notion of set inversion, a new state estimator is presented, which evaluates a set estimate guaranteedto contain all values of the state that are consistent with the available observations, given the perturbation and noise bounds and a set containing the initial value of the state. To the best of our knowledge, it is the first estimator for which this claim can be made. The precision of the set estimate can be improved, at the cost of more computation. Theoretical properties of the estimator are studied, and computer implementation receives special attention. A simple illustrative example is treated. Copyright © 2002 John Wiley & Sons, Ltd.

Parameter or state estimation should take into account the fact that the model is an approximation of reality and that the data are corrupted by noise. In this paper, each uncertain quantity is assumed to belong to a known set. The problem, known as parameter or state bounding, is then to characterize the setof all parameter or state vectors that are consistent with the model structure, data and error bounds. A description of how interval analysis can be used to find guaranteed estimates in a nonlinear context is provided. The main notions of interval analysis are first recalled very briefly. The simpler problem of parameter estimation is then considered. State estimation, which contains parameter tracking as a special case, is treated next. A simple illustrative example is finally presented.

This paper deals with the minimax parameter estimation of nonlinear parametric models from experimental data. Taking advantage of the special structure of the minimax problem, a new efficient and reliable algorithm based on interval constraint propagation is proposed. As an illustration, the ill-conditioned problem of estimating the parameters of a two-exponential model is considered.

In this paper, the problem of interest is to find a path with given endpoints such that the path lies inside a compact set S given by nonlinear inequalities. The proposed approach uses interval analysis for characterizing S by subpavings (union of boxes) and graph algorithms for finding short feasible paths. As an illustration, the problem of finding collision-free paths for a polygonal rigid object through a space that is cluttered with segment obstacles is considered.

This paper deals with the determination of the position and orientation of a mobile robot from distance measurements provided by a belt of onboard ultrasonic sensors. The environment is assumed to be two-dimensional, and a map of its landmarks is available to the robot. In this context, classical localization methods have three main limitations. First, each data point provided by a sensor must be associated with a given landmark. This data-association step turns out to be extremely complex and time-consuming, and its results can usually not be guaranteed. The second limitation is that these methods are based on linearization, which makes them inherently local. The third limitation is their lack of robustness to outliers due, e.g., to sensor malfunctions or outdated maps. By contrast, the method proposed here, based on interval analysis, bypasses the data-association step, handles the problem as nonlinear and in a global way and is (extraordinarily) robust to outliers.

This paper deals with robust and autonomous robot tracking using distance measurements provided by a belt of on-board ultrasonic sensors. The measurements errors are assumed to be bounded. The method presented uses a set-valued nonlinear state estimator. As a Kalman filter, it alternates prediction based on past data and correction to take new measurements into account. Special attention is paid to the treatment of outliers due, e.g., to a partially outdated map or to faulty sensors.

Discrete-event systems are driven by events and generate events. To describe their evolution, the dater approach associate to each event a sequence of dates, namely a dater, corresponding to the dates at which the event occurs. In this paper, we show that for a large class of discrete-event systems, the dater approach makes it possible to cast the characterization of the set of all parameters that are consistent with some collected dater, in a bounded-error context, into a set-inversion framework. Set inversion consists of characterizing the reciprocal image of a given set by a known function. Provided that an inclusion function is known for the function to be inverted, the characterization can be performed by the interval-based algorithm SIVIA. A short presentation of this algorithm is recalled in this paper. The approach is illustrated through three examples.

Presents information on interval analysis which is used to characterize the set of all input sequences with a given length that drives a nonlinear discrete-time state-space system from a given initial state to a given set of terminal states. Requirements of interval analysis; Methodology used in the research; Results of the research.

This paper presents a method for determining the area explored by a line-sweep sensor during an area-covering mission in a two-dimensional plane. Accurate knowledge of the explored area is crucial for various applications in robotics, such as mapping, surveillance, and coverage optimization. The proposed method leverages the concept of coverage measure of the environment and its relation to the topological degree in the plane, to estimate the extent of the explored region. In addition, we extend the approach to uncertain coverage measure values using interval analysis. This last contribution allows for a guaranteed characterization of the explored area, essential considering the often critical character of area-covering missions. Finally, this paper also proposes a novel algorithm for computing the topological degree in the 2-dimensional plane, for all the points inside an area of interest, which differs from existing solutions that compute the topological degree for single points. The applicability of the method is evaluated through a real-world experiment. [ABSTRACT FROM AUTHOR]

Linear matrix inequalities (LMIs) comprise a large class of convex constraints. Boxes, ellipsoids, and linear constraints can be represented by LMIs. The intersection of LMIs are also classified as LMIs. Interior-point methods are able to minimize or maximize any linear criterion of LMIs with complexity, which is polynomial regarding to the number of variables. As a consequence, as shown in this paper, it is possible to build optimal contractors for sets represented by LMIs. When solving a set of nonlinear constraints, one may extract from all constraints that are LMIs in order to build a single optimal LMI contractor. A combination of all contractors obtained for other non-LMI constraints can thus be performed up to the fixed point. The resulting propogation is shown to be more efficient than other conventional contractor-based approaches.

The principle behind VSLAM applications like 3D object reconstruction or indoor mapping is to estimate the spatial transformation between two large clouds of points, which represent two poses of the same scene. They can further be processed to obtain detailed surfaces. Since its introduction in 1992, the standard algorithm for finding the alignment between two point clouds is ICP (Iterative Closest Point) and its variants, combined with RANSAC (RANdom SAmple Consensus). This paper presents a new approach using interval analysis. The idea is to define large intervals for the transformation parameters between the poses then to successively contract those intervals using the equations of the transformation of corresponding points between the poses. To contract those intervals faster, we added an IMU (Inertial Measurement Unit) to our system so the initial intervals of the parameters are already small before applying the contractions. We implemented our algorithm using the middleware ROS (Robot Operating System) and stated our performances.