LexLS

A fast C++ solver for lexicographic least-squares problems based on the lexicographic QR (l-QR) presented in the paper Efficient resolution of potentially conflicting linear constraints in robotics, by D. Dimitrov, A. Sherikov and P.-B. Wieber.

Lexicographic Least-Squares

Let's consider sets of constraints , potentially conflicting. We consider that each of these sets have a different priority level, where 1 has the higher priority and p the lower. We are looking for a solution that first minimize the violation of , in the least-square sense (that is minimizing such that is verified), then minimizing the violation of without increasing and so on.

Formally this can be written as

LexLS solves the above problem with a primal, active-set approach, where all priority levels are tackled together.

Scope

LexLS was optimized for problems with few changes of active set, leveraging warm-start to limit the number of iterations between the resolution of closely related problems as can be found in e.g succesive inverse kinematics problems. The l-QR decomposition is highly optimized to run from scratch, with speed comprised between Eigen's LU and QR, depending on the number of priority levels. No update mechanism has been implemented yet, so that each iteration of the solver performs a full decomposition.

Build and use with CMake

Dependencies

• Eigen

For documentation generation:

• Doxygen (sudo apt install doxygen on Debian-based systems)
• pdflatex with extra packages and extra fonts (sudo apt install texlive-base texlive-science texlive-fonts-extra on Debian-based systems)

For GNU Octave bindings, the software should be installed and mex correctly setup to build C++ code.

For MATLAB bindings, the software should be installed and mex correctly setup to build C++ code.

Building

This package can be built with CMake:

mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo -GNinja
ninja && sudo ninja install

You can customize the build with the following options:

• BUILD_TESTING build unit tests (ON by default)
• INSTALL_HTML_DOCUMENTATION build and install the HTML documentation (ON by default, automatically skipped if doxygen is missing)
• INSTALL_PDF_DOCUMENTATION build and install the PDF documentation (ON by default, automatically skipped if pdflatex is missing, does not check for missing texlive packages)
• BUILD_OCTAVE_BINDINGS build and install bindings for the GNU Octave software (OFF by default)
• BUILD_MATLAB_BINDINGS build and install bindings for the MATLAB software (OFF by default)

Using it in your project

Once the project is installed, you can use the following to use lexls in your project:

find_package(lexls REQUIRED)
target_link_libraries(MyProject PUBLIC lexls::lexls)

Credits

The solver was mainly implemented by Dimitar Dimitrov, with additionnal code from Alexander Sherikov and Nestor Bohorquez, with supervision from Pierre-Brice Wieber.