The Codac manual

Welcome to the Codac website. This manual is currently under construction. We are actively working on it and appreciate your patience as we build a comprehensive guide.

Codac (Catalog Of Domains And Contractors) is a C++/Python/Matlab library providing tools for constraint programming over reals, trajectories and sets. It has many applications in parameter estimation, guaranteed integration, robot localization, and provides reliable outputs.

The toolbox allows to approximate feasible solutions of non-linear and/or differential systems. Since the solution of these complex systems cannot generally be calculated exactly, Codac uses numerical analysis to compute the bounds of sets of feasible solutions. The assets are guarantee (computations are guaranteed to never lose solutions, due to the rigorous interval arithmetic) and thus exhaustiveness (if multiple values are possible, all of them are characterized).

Codac can thus be used to establish numerical proofs, or to approximate solutions of complex systems mixing variables of different natures such as reals, vectors, trajectories, uncertain sets, graphs, etc. Most developers of the library are motivated by mobile robotics problems for which Codac offers new perspectives.

Recent advances in interval methods have been done by the community, and the Codac library gathers a part of related state-of-the-art implementations with the objective to make them easy to combine.

Short example: solving an equation

One of Codac’s applications is to solve systems of equations. The following example [1] computes a reliable outer approximation of the solution set of the equation system:

(1)\[\begin{split}\left( \begin{array}{c} -x_3^2+2 x_3 \sin(x_3 x_1)+\cos(x_3 x_2)\\ 2 x_3 \cos(x_3 x_1)-\sin(x_3 x_2) \end{array}\right)=\mathbf{0}.\end{split}\]

The solution set is approximated from an initial box \([\mathbf{x}_0]=[0,2]\times[2,4]\times[0,10]\). The bisection involved in the paving algorithm is configured to provide boxes with a precision \(\epsilon=4\times 10^{-3}\).

from codac import *

x = VectorVar(3)
f = AnalyticFunction([x], [
  -(x[2]^2)+2*x[2]*sin(x[2]*x[0])+cos(x[2]*x[1]),
  2*x[2]*cos(x[2]*x[0])-sin(x[2]*x[1])
])

ctc = CtcInverse(f, [0,0])
draw_while_paving([[0,2],[2,4],[0,10]], ctc, 0.004)

The result is a set of non-overlapping boxes containing the set of feasible solutions of (1). The following figure shows a projection of the computed set.

_images/example_malti.png

Outer approximation of the solution set, computed with CtcInverse. Blue parts are guaranteed to be solution-free. Computation time: 0.609s. 3624 boxes.

Short example: solving an inequality

The previous example showed a way of solving systems of the form \(\mathbf{f}(\mathbf{x})=\mathbf{0}\). The library also provides tools for solving generic systems expressed as \(\mathbf{f}(\mathbf{x})\in[\mathbf{y}]\) where \([\mathbf{y}]\) is an interval or a box.

The following code allows to compute the set of vectors \(\mathbf{x}\in\mathbb{R}^2\) satisfying the inequality:

(2)\[x_1\cos(x_1-x_2)+x_2 \leqslant 0\]
x = VectorVar(2)
f = AnalyticFunction([x], x[0]*cos(x[0]-x[1])+x[1])
sep = SepInverse(f, [-oo,0])
draw_while_paving([[-10,10],[-10,10]], sep, 0.004)
_images/example_ineq.png

Approximation of an enclosure of the solution set computed with SepInverse. The blue parts are guaranteed to have no solution, while any vector in the green boxes is a solution to the inequality. Computation time: 0.0809s.

Contributors

This list is in alphabetical order by surname.

We appreciate all contributions, whether they are code, documentation, bug reports, or suggestions. If you believe you should be listed here and are not, please contact us to update the list.

Provisional Plan

Below is a provisional plan for the structure of this manual. Some pages are already available. Please note that some sections may change or be added as we continue to develop the content.


Overview of Codac

  • Intervals and constraints

  • The Codac framework

  • Target audience

User manual

How-to guides

  • Robotics

    • Non-linear state estimation

    • State estimation by solving data association

    • Range-only SLAM

    • Explored area

    • Loop detections and verifications

  • Geometry

    • 2d shape registration

  • Dynamical systems

    • Lie symmetries for guaranteed integration

    • Solving a discrete Lyapunov equation

    • Stability analysis of a non-linear system

Development

How to cite Codac

The main reference to the Codac library is the following paper:

@article{codac_lib,
  title={The {C}odac Library},
  url={https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/4388},
  DOI={10.14232/actacyb.302772},
  journal={Acta Cybernetica},
  volume={26},
  number={4},
  series = {Special Issue of {SWIM} 2022},
  author={Rohou, Simon and Desrochers, Benoit and {Le Bars}, Fabrice},
  year={2024},
  month={Mar.},
  pages={871-887}
}