added: NonLinMPC and MovingHorizonEstimator integration with DI.jl

[franckgaga]

Nonlinear MPC and moving horzion estimator now use DifferentiationInterface.jl

Both NonLinMPC and MovingHorizonEstimator constructor now accept a gradient and jacobian keyword arguments, receiving a AbstractADType to switch the backend of the objective gradient and constraint Jacobians, respectively. Note that the nonlinear inequality and equality constraints will both use the backend provided by the jacobian argument. The possibility to provide a hessian will be added in a future PR (the LBFGS approximation is used inside Ipopt for now, as it was the case before)

By default, denses AutoForwardDiff() is use everywhere, except for NonLinMPC with non-SingleShooting transcription method, in which this backend is used:

AutoSparse(
    AutoForwardDiff(); 
    sparsity_detector  = TracerSparsityDetector(), 
    coloring_algorithm = GreedyColoringAlgorithm()
)

For both objects, the differentiation make use of DifferentiationInterface.Constant() and DifferentiationInterface.Cache() functionalities. As a consequence, they does not rely on PreallocationTools.DiffCaches anymore. But, I still need to keep this dependency since linearize! and all DiffSolvers still rely on them for now.

Documentation now use DocumenterInterLink.jl

Some URL were very long in the docstrings. The are now way shorter. It also ease the maintenance for the documentation of external dependencies.

The doc preview is here: https://juliacontrol.github.io/ModelPredictiveControl.jl/previews/PR174

[codecov-commenter]

Codecov Report

Attention: Patch coverage is 99.32432% with 1 line in your changes missing coverage. Please review.

Project coverage is 98.87%. Comparing base (c12d7bc) to head (9d0b0ce).

Files with missing lines	Patch %	Lines
src/controller/execute.jl	85.71%	1 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #174      +/-   ##
==========================================
+ Coverage   98.85%   98.87%   +0.01%     
==========================================
  Files          25       25              
  Lines        4180     4160      -20     
==========================================
- Hits         4132     4113      -19     
+ Misses         48       47       -1     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[gdalle]

Heads up, DI v0.6.46 supports nested tuples and named tuples of arrays as caches

[franckgaga]

Thanks for the info, right now I do:

mycontext = (
    Constant(a),
    Cache(b),
    Cache(c),
    Cache(d),
)
grad_prep = prepare_gardient!(myfunc, grad_backend, x, mycontext...; strict=Val(true))

and a similar splatting for the context in gradient!. Do you this splatting is problematic for the performance ? I did some quick benchamarks and I measured no impact at all.

[gdalle]

I don't think it is problematic, but for some users it is a bit painful: when you have tens of caches you may want to structure the more neatly, so I give that option too.

[franckgaga]

Alright thanks! I thinks it's neat enough in the code like that.

[franckgaga]

@baggepinnen It's ready to be merged, if you have some comments. You can have a look a NonLinMPC and MovingHorizonEstimator documentation (additionnal details in their respective Extended Help)

edit: I'm running the benchmarks of our papers in this version, and there is no significative difference on the performances, good news ❤️

[gdalle]

edit: I'm running the benchmarks of our papers in this version, and there is no significative difference on the performances, good news ❤️

If you want to play around some more, a parameter that might impact performance is the coloring algorithm used by SparseMatrixColorings, more specifically the vertex ordering. Feel free to switch the default NaturalOrder() and see if it makes a difference with SMC.ncolors(jacobian_prep). Roughly speaking, the sparse autodiff complexity scales with the number of colors $c$ (or with $\lceil c / 12 \rceil$ for ForwardDiff).

[franckgaga]

If you want to play around some more, a parameter that might impact performance is the coloring algorithm used by SparseMatrixColorings, more specifically the vertex ordering. Feel free to switch the default NaturalOrder() and see if it makes a difference with SMC.ncolors(jacobian_prep). Roughly speaking, the sparse autodiff complexity scales with the number of colors c (or with ⌈ c / 12 ⌉ for ForwardDiff).

I did not played a lot with sparse jacobians for now. The pendulum exemples in our paper was small in term of number of decision variables, thus it is expected that no matter the chosen coloring/compression/etc algorithm, it will always be a bit slower then a dense formulation (for the same AD backend). It's like classical matrix operations e.g. product: if the matrices are relatively small, dense operations are generally faster even if they include many zeros.

And that was indeed the case from my quick tests. That is, on the inverted pendulum model with a control horizon of $H_c=2$ and a prediction horizon of $H_p=20$, the fastest to the slowest:

1. Single shooting transcription (dense formulation of the problem) with dense ForwardDiff, about 12 ms per time step
2. Multiple shooting transcription (sparse formulation of the problem) with dense ForwardDiff, about 20 ms per time step
3. Multiple shooting transcription (sparse formulation of the problem) with sparse ForwardDiff, about 29 ms per time step

I may improve a little bit 3. by tweaking the colouring algorithm here, but IMO that's not the good case study to adequately benchmark sparse computations.

[franckgaga]

@gdalle I just read that for Constant() context some backends requires Number or AbstractArray.

Right now I pass a mpc::NonLinMPC object in the Constant arg. I understand that it won't work with some backends ? Do you know which one ?

[gdalle]

I think it will only be symbolic backends. I should update the docstring. Not a hard limitation either, I just didn't get around to it.