search

ethz-adrl / control-toolbox

The Control Toolbox - An Open-Source C++ Library for Robotics, Optimal and Model Predictive Control
BSD 2-Clause "Simplified" License
1.41k stars 308 forks source link

[Feature Request] DDP Implementation #60

Open acxz opened 4 years ago

acxz commented 4 years ago

I would like to use a very fast C++ library for DDP (differential dynamic programming) but I couldn't find one online. I was hoping the toolbox has it, but I couldn't find it here either. If you guys are familiar with any C++ DDP implementations out there, could you recommend them to me?

In any case, I believe adding DDP to the control-toolbox would be a great feature. Especially if it utilizes Auto-Diff codegen.

markusgft commented 4 years ago

Hi @acxz, thanks for your interest in the CT! We did not implement DDP and actually we are not planning to add DDP support. The CT implements iLQR, for example, which is a Gauss-Newton variant of DDP, and avoids many of the issues of exact-Hessian methods. In our opinion, for most applications where you would use DDP, iLQR gets the job done, too!

acxz commented 4 years ago

Ahhh okay. In that case, I would like to try to add a DDP implementation to this toolbox. Would you be open to accepting a PR for DDP, if I get around to it?

markusgft commented 4 years ago

Sure!

acxz commented 4 years ago

@markusgft I am trying to incorporate DDP into CT, but I am getting a bit confused. I was wondering if you can point me in the right direction. Should I be editing this file to incorporate the DDP case in addition to the iLQR case?

acxz commented 4 years ago

Okay digging around a bit more, and I think I need to create a DDP version of this file (GNRiccatiSolver-impl.hpp), in addition to incorporating DDP where iLQR is being used. Can I ask what the GN stands for in GNRiccatiSolver?

markusgft commented 4 years ago

GN = Gauss Newton. Before touching anything, I would recommend you to carefully study the associated publication. For DDP you would need to modify the LQ-approximation part to become a QQ-approximation. The modifications for this are non-trivial, e.g. you would need to introduce base classes for quadratized dynamics, implement automatic differentiation for that type of class, modify the setters for the NLOC backend, and finally you would need to incorporate a few advanced regularization schemes in order to keep the second order algorithm stable. Again, I would like to point out to you, that from a numeric perspective, the Gauss-Newton variant is more easy to understand, typically more robust and faster, while only loosing a little bit of local contraction rate. Why dont you just go with iLQR?

markusgft commented 4 years ago

I assume I can close this now.

acxz commented 4 years ago

Hey @markusgft im trying to slowly chip away at this. I was wondering if I could ask you a question. You mention that

modify the LQ-approximation part to become a QQ-approximation

Does this mean that we don't want a separate series of files for QQ-approx? As in we don't add a QQOCProblem along with LQOCProblem but make the new QQOCProblem generic enough for the current LQOCProblem?

Right now what I am doing is just adding the corresponding QQ files along with the LQ files so that I can understand how the files fit together and I still have the LQ to compare against. Once I essentially duplicate the LQ files into their QQ counterparts, I'll actually start editing the QQ logic to make it truly QQ and compare the results with the original LQ files which will still be there.

markusgft commented 4 years ago

Hi @acxz, for developing, I would probably choose the same approach like you. In the end, however, once you have a working implementation, we should think of how to merge it all together with as little as possible code dublication. There is also one thing we should have in the back of our minds - I am currently drafting version 3.0.3, which will see a quite significant change in the design pattern of the template parameters. 3.0.3 is not really in a state right now which would be useful for you, so I cannot even recommend you to look at it -- but we will have some significant coordination work to do to put our things together! Best

acxz commented 4 years ago

I see, yes reducing code duplication should def be priority once I can verify and compare both LQ and QQ code.

Ah thanks for letting me know about 3.0.3. When do you think it will be released? I think right now I still have much to learn about the inner workings of the codebase, so it will be better if I continue hacking away at it on 3.0.2, so then when we do have to merge things I can better understand how the code has changed and where the appropriate logic should go in 3.0.3.

Thanks for the advice, as I get forward along I'll be pinging you more questions if you are fine with that, haha.

markusgft commented 4 years ago

Sure, please do not hesitate to come back with questions!

acxz commented 4 years ago

@markusgft another quick semantics question. What variable convention should I use for the quadratization? For linearization the code has Ax + Bu, where A and B are the linearized matrices. I was thinking of using: x^T Fxx x + 2 * x^T Fxu u + u^T Fuu u + Fx x + Fu u Would you be fine with this convention of using F with the appropriate differentiation variables as subscripts?

Also is it proper to use the word quadratizer? I have been using that to replace the linearizer.

markusgft commented 4 years ago

Sure! And just in case, such small things can always be refactored quickly!

On Sat, May 16, 2020, 18:16 acxz notifications@github.com wrote:

@markusgft https://github.com/markusgft another quick semantics question. What variable convention should I use for the quadratization? For linearization the code has Ax + Bu, where A and B are the linearized matrices. I was thinking of using: x^T Fxx x + 2 * x^T Fxu u + u^T Fuu u + Fx x + Fu u Would you be fine with this convention of using F with the appropriate differentiation variables as subscripts?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ethz-adrl/control-toolbox/issues/60#issuecomment-629669708, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADJQVFDAR2VWLEPDIXLTE2DRR2355ANCNFSM4JSFGCCQ .