# Introduction to the concepts of CP and IA

## Constraint programming

Codac is designed to deal with static and dynamical systems that are usually encountered in robotics.
It stands on constraint programming: a paradigm in which the properties of a solution to be found (*e.g.* the pose of a robot, the location of a landmark) are stated by constraints coming from the equations of the problem.

Then, a solver performs **constraint propagation** on the variables and provides a reliable set of feasible solutions corresponding to the considered problem. In this approach, the user concentrates on *what* is the problem instead of *how* to solve it, thus leaving the computer dealing with the *how*. The strength of this declarative paradigm lies in its simpleness, as it allows one to describe a complex problem without requiring the knowledge of resolution tools coming with specific parameters to choose.

The following figure presents a conceptual view of a constraint propagation.

### Variables

The unknown solutions of a system are reals \(x\), vectors \(\mathbf{x}\), or in the dynamic case: so-called trajectories denoted by \(x(\cdot)\), or \(\mathbf{x}(\cdot)\) in the vector case.

Dot notation \((\cdot)\)

Note that in the literature, the dot notation \((\cdot)\) may be used to represent the independent system variable (time). This notation may be chosen in order to clearly distinguish a whole trajectory \(\mathbf{x}(\cdot):\mathbb{R}\to\mathbb{R}^n\) from a local evaluation: \(\mathbf{x}(t)\in\mathbb{R}^n\). Indeed, the time \(t\) may also be a variable to be estimated.

In the constraint programming approach, the estimation of a variable consists in computing its reliable enclosure set, defined here as an interval of values.
The obtained set is said **reliable**: the resolution guarantees that no solution can be lost during the solving process, according to the equations defining the problem. In other words, a variable \(x\) to be estimated will surely be enclosed in the resulting set \([x]\).

### Domains

As depicted in the figure, a variable is known to be enclosed in some domain \(\mathbb{X}\) on which we will apply constraints. In Codac, the domains are represented by the following sets:

for reals \(x\), domains are intervals \([x]\);

for vectors \(\mathbf{x}\), we define boxes \([\mathbf{x}]\);

for trajectories \(x(\cdot)\), we introduce tubes \([x](\cdot)\).

### Constraints

The approach consists in defining the problem as a set of constraints. They usually come from state equations, numerical models, or measurements. In mobile robotics, we usually have to deal with:

non-linear functions: \(x_3=\cos\big(x_1+\exp(x_2)\big)\)

differential equations: \(\dot{x}(\cdot)=f\big(x(\cdot),u(\cdot)\big)\)

temporal delays: \(x(t)=y(t-\tau)\)

time uncertainties: \(x(t)=y\), with \(t\in[t]\)

*etc.*

The aim of Codac is to easily deal with these constraints in order to eventually characterize sets of variables compliant with the defined rules.
Each constraint comes from equations or measurements. And each constraint will be applied by means of an operator called **contractor**.

### Contractors

Contractors are operators designed to reduce domains without losing any solution consistent with the related constraint. In Codac, the contractors act on intervals, boxes and tubes.

Codac already provides a catalog a contractors that one can use to deal with many applications. New contractors can also be designed and embedded in this framework without difficulty.

Constraint programming *vs* probabilistic methods

The approach does differ from probabilistic methods in regards of the nature of the estimated solution. Probabilistic methods compute a punctual potential solution – for instance a vector – while in set-membership ones, it is the **set of all feasible solutions** that is evaluated, and thus an infinity of potential solutions.

Another main distinction lies in the way things are computed: with set-membership methods, estimations are not randomly performed. **Computations are deterministic**: given a set of parameters or inputs, algorithms will always output the same result.

### Reliable outputs

One of the advantages of this set-membership approach is the reliable outputs that are obtained.
By *reliable*, we mean that all sources of uncertainties are taken into account, including:

model parameter uncertainties

measurement noise

uncertainties related to time discretization

linearization truncations

approximation of real numbers by floating-point values

The outcomes are intervals and tubes that are guaranteed to contain the solutions of the system. This is well suited for proof purposes as we always consider worst-case possibilities when delineating the boundaries of the solution sets.

The main drawback however, is that we may obtain large sets that may not be useful to characterize the solutions of the problem. We call this *pessimism*. This can be overcome by reformulating some constraints or by using bisections on sets.

### Getting started

Now, to get ready for the tutorial, you need to install the Codac 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: