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: .. math:: :label: eq:malti \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}. The solution set is approximated from an initial box :math:`[\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 :math:`\epsilon=4\times 10^{-3}`. .. tabs:: .. code-tab:: py 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) .. code-tab:: c++ #include using namespace codac2; int main() { VectorVar x(3); AnalyticFunction f { {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]) } }; CtcInverse ctc(f, {0,0}); draw_while_paving({{0,2},{2,4},{0,10}}, ctc, 0.004); } .. code-tab:: matlab import py.codac4matlab.* x = VectorVar(3); f = AnalyticFunction({x}, vec( ... -sqr(x(3))+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)) ... )); ctc = CtcInverse(f, IntervalVector({0,0})); draw_while_paving(IntervalVector({{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 :eq:`eq:malti`. The following figure shows a projection of the computed set. .. figure:: manual/example_malti.png :width: 400px 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 :math:`\mathbf{f}(\mathbf{x})=\mathbf{0}`. The library also provides tools for solving generic systems expressed as :math:`\mathbf{f}(\mathbf{x})\in[\mathbf{y}]` where :math:`[\mathbf{y}]` is an interval or a box. The following code allows to compute the set of vectors :math:`\mathbf{x}\in\mathbb{R}^2` satisfying the inequality: .. math:: :label: eq:ineq x_1\cos(x_1-x_2)+x_2 \leqslant 0 .. tabs:: .. code-tab:: py 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) .. code-tab:: c++ VectorVar x(2); AnalyticFunction f({x}, x[0]*cos(x[0]-x[1])+x[1]); SepInverse sep(f, {-oo,0}); draw_while_paving({{-10,10},{-10,10}}, sep, 0.1); .. code-tab:: matlab x = VectorVar(2); f = AnalyticFunction({x}, x(1)*cos(x(1)-x(2))+x(2)); sep = SepInverse(f, Interval(-oo,0)); draw_while_paving(IntervalVector({{-10,10},{-10,10}}), sep, 0.1); .. figure:: manual/example_ineq.png :width: 400px 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. .. hlist:: :columns: 4 * Auguste Bourgois * `Cyril Bouvier `_ * `Quentin Brateau `_ * Gilles Chabert * `Julien Damers `_ * Benoît Desrochers * `Peter Franek `_ * `Maël Godard `_ * `Nuwan Herath M. `_ * `Luc Jaulin `_ * `Fabrice Le Bars `_ * `Morgan Louédec `_ * `Damien Massé `_ * `Bertrand Neveu `_ * Verlein Radwan * `Andreas Rauh `_ * `Simon Rohou `_ * `Joris Tillet `_ * `Gilles Trombettoni `_ * `Christophe Viel `_ * `Raphael Voges `_ 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 ----------- * :ref:`sec-install` * :ref:`sec-install-py` * :ref:`sec-install-cpp` * :ref:`sec-install-matlab` * :ref:`sec-intervals` * What is an interval? * :ref:`sec-intervals-class` * Boolean intervals * Linear algebra * Vector, Matrix * IntervalVector, IntervalMatrix * Matrix operations and basic linear solving * :ref:`sec-linear-inversion` * :ref:`sec-linear-lu` * C++: efficient matrix operations using Eigen * :ref:`sec-functions` * :ref:`sec-functions-analytic` * :ref:`sec-functions-analytic-class` * :ref:`sec-functions-analytic-operators` * Extension to custom expressions * Temporal functions * Set-membership functions * The class SetMembershipFunction * Extension to custom expressions * Tubes * What is a tube? * Temporal domains * The Tube classes * The Trajectory classes * Increasing performances using views * Contractors * What are contractors? * How to build a contractor * Basic contractors * CtcIdentity * CtcEmpty * CtcLazy * CtcFixpoint * Linear contractors * CtcGaussElim * CtcGaussSeidel * CtcLinearPrecond * Set contractors * CtcUnion * CtcInter * CtcQInter * CtcCartProd * CtcProj * CtcNot * CtcAction * Analytic contractors * Directed operators * CtcInverse * CtcInverseNotIn * Geometric contractors * :ref:`sec-ctc-geom-ctcdist` * :ref:`sec-ctc-geom-ctcpolar` * CtcSegment * CtcPolygon * CtcPointCloud * CtcEllipse * CtcCross / CtcNoCross * Shape contractors * CtcCtcBoundary * CtcWrapper * CtcImage * CtcDiscreteSet * Temporal contractors * Using static contractors on tubes * CtcDeriv * CtcEval * CtcDelay * CtcLinobs * CtcLohner * CtcPicard * CtcChain * CtcDiffInclusion * Separators * What are separators? * How to build a separator * Basic separators * SepCtcPair * Set separators * SepUnion * SepInter * SepQInter * SepCartProd * SepProj * SepNot * SepAction * Analytic separators * SepInverse * SepTransform * Geometrical separators * SepPolarCart or SepCartPolar * SepPolygon * SepEllipse * SepCross * Shape separators * SepCtcBoundary * SepWrapper * SepImage * Contractors obtained from separators * CtcInnerOuter * Towards thick separators * Pavers * The SIVIA algorithm * Pavers for contractors and separators * Paving structures * RegularPaving * NonRegularPaving * Contractor Networks * What is a CN? * The ContractorNetwork class * :ref:`sec-geom` * :ref:`sec-geom-utils` * :ref:`sec-geom-segment` * :ref:`sec-geom-polygon` * Polyhedron * :ref:`sec-ellipsoids` * :ref:`sec-ellipsoids-intro` * :ref:`sec-ellipsoids-class` * Topology * Extract connected subsets from pavings * Topological degree: verify zeros of an inclusion function * :ref:`sec-graphics` * :ref:`sec-graphics-2d-figures` * :ref:`sec-graphics-functions` * :ref:`sec-graphics-colors` * :ref:`sec-graphics-vibes` * :ref:`sec-graphics-ipe` * :ref:`sec-graphics-3d` * :ref:`sec-tools` * Serialization tools * :ref:`sec-tools-registration` * Codac extensions * :ref:`sec-extensions-capd` * Interface with the IBEX library * Sympy (symbolic computation) * :ref:`sec-seealso` * Frequently Asked Questions * :ref:`sec-seealso-performances` * Low-level interval library * References * Related papers * Contributors * How to cite Codac 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 ----------- * :ref:`sec-dev-info` * Changelog * C++ API .. .. toctree:: .. :hidden: .. :caption: Overview of Codac .. :maxdepth: 3 .. .. Intervals and constraints .. The Codac framework .. Target audience .. toctree:: :hidden: :caption: User manual :maxdepth: 2 manual/installation/index.rst manual/intervals/index.rst manual/linear/index.rst manual/functions/index.rst manual/contractors/index.rst manual/geometry/index.rst manual/ellipsoids/index.rst manual/visualization/index.rst manual/tools/index.rst manual/extensions/index.rst manual/seealso/index.rst .. linear/index.rst .. functions/index.rst .. tubes/index.rst .. .. toctree:: .. :hidden: .. :maxdepth: 3 .. .. contractors/index.rst .. separators/index.rst .. .. toctree:: .. :hidden: .. :maxdepth: 2 .. .. pavers/index.rst .. cn/index.rst .. geometry/index.rst .. topology/index.rst .. references/index.rst .. .. toctree:: .. :hidden: .. :caption: How-to guides .. :maxdepth: 3 .. .. howto/robotics/index.rst .. howto/geometry/index.rst .. howto/dynamical/index.rst .. toctree:: :hidden: :caption: Tutorial :maxdepth: 3 tuto/cp_robotics/index.rst .. toctree:: :hidden: :caption: Development :maxdepth: 3 development/info_dev.rst .. .. Changelog .. C++ API How to cite Codac ^^^^^^^^^^^^^^^^^ The main reference to the Codac library is `the following paper `_: .. code-block:: none @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} }