I would not recommend to invent the wheel again. There are many powerful methods

to solve optimal control problems numerically (since most of them do not have analytical solutions).

I would suggest to solve firstly the problem with a direct method, also called first-discretize-then-optimize methods. Objective function and ODEs as well as inequality constraints are discretized by simple methods, e.g. explicit or implicit Euler with fixed step size. Then solve the resulting NLP problem. Good software packages can be obtained from Matthias Gerdts (Munich), Christoph Bueskens (Bremen) or John Betts (Seattle). Or simply use the programming language AMPL in connection with IPOPT of Waechter and Biegler. The latter one is open source, while AMPL costs a little bit. We have made good experiences with the latter one. However, your problem is with free terminal time and those problems cannot easily be solved by AMPL/IPOPT to our experiences.

If your problem is very complex, I would not suggest to use an indirect method such as multiple shooting unless you really need extremely precise results, for example for applications in aeronautics. Here, it is often extremely difficult to find appropriate initial guesses, particularly for the adjoints. (I was one of the first who have used multiple shooting for complex optimal control problems in aeronautics.)

I would not recommend to invent the wheel again. There are many powerful methods

to solve optimal control problems numerically (since most of them do not have analytical solutions).

I would suggest to solve firstly the problem with a direct method, also called first-discretize-then-optimize methods. Objective function and ODEs as well as inequality constraints are discretized by simple methods, e.g. explicit or implicit Euler with fixed step size. Then solve the resulting NLP problem. Good software packages can be obtained from Matthias Gerdts (Munich), Christoph Bueskens (Bremen) or John Betts (Seattle). Or simply use the programming language AMPL in connection with IPOPT of Waechter and Biegler. The latter one is open source, while AMPL costs a little bit. We have made good experiences with the latter one. However, your problem is with free terminal time and those problems cannot easily be solved by AMPL/IPOPT to our experiences.

If your problem is very complex, I would not suggest to use an indirect method such as multiple shooting unless you really need extremely precise results, for example for applications in aeronautics. Here, it is often extremely difficult to find appropriate initial guesses, particularly for the adjoints. (I was one of the first who have used multiple shooting for complex optimal control problems in aeronautics.)

Thanks Hans for the answer. I am actually using this for a 12 dof UAV model. So which package you would suggest the most?

I am also looking for real time implementation of the controller.

Thanks.

Dear Mohamed,

First I would like to know a little bit more about the size of your problem.

Is it correct that you have at least 12 state variables? How many control variables do you have? Could you please name the variables in technical terms; this might perhaps help me? Do they enter the functional and the ordinary differential equations linearly or nonlinearly? How long is the expected flight time? How many control, resp. state constraints or mixed control-states-constraints do you have.

Based on these facts I might give you some more advice.

Best regards,

Hans Josef

Dear Prof. Hans,

I appreciate that you are taking the trouble to help answering my questions.

Here are the answers:

1- The model has 12 states (i.e. there will be also 12 adjoint variables)

2- The cost functional is not set yet, but let's say I'd like to minimize the energy of the controls, so I'd use a simple one like int(u^2)

3- I have three controls: aileron and elevator deflections, and throttle command.

4- the controls the controls enter the ODE system linearly

5- given the previous cost function, I CAN get an analytical expression of the optimal controls when I derive the Hamiltonian w.r.t each control and equate it to zero, for each control.

6- The dynamical system for the adjoint variables can be written as linear time-variant systems (i.e. d(lambda)/dt=A(t)*lambda); where A(t) is a 12x12 matrix that depends on the system states X(t), and 'lambda' is the vector of adjoint variables.

7-As you can see I have constraints on the controls, basically saturations for the control surfaces, and the max & min thrust.

8- I also will impose constraints on the final conditions of the states, for example I would like to optimize a landing scenario for the UAV. So, I want it to have zero speeds in the vertical velocities at the touchdown + constraints on the position such that it doesn't leave the run way+ constraint on the attitude angles to insure safe level landing. Also, some constraints on the max body rates such that they don't exceed the UAV capabilities. Some thing in that sense!

9- for the flight time, currently we have a prototype electric-UAV that we use for testing, and the maximum flight time that we achieved up to now is around 2 minutes, but it actually can go more, and for the future, it will definitely go for larger time scale using other airframes.

That's a brief of the case. I hope that clarifies the picture a bit, and thank you again for your kind help.

Dear Mohamed,

well then start with a direct method as described in my first answer. If you use the energy functional your controls do not enter functional AND odes linearly, so you will not have singular controls, instead your Hamiltonian is quadratical in the controls, so that you can easily obtain the optimal control laws, as you have found.

After solving the problem with a direct method based on a transcription of the infinite dimensional optimization problem by discretizing it into a finite dimensional optimal control problem and solving it by an NLP method, take the estimates of the adjoint variables provided by that direct method to verify your optimal control laws a posteriori. Compare the approximate optimal control values provided by the direct method with the results obtained via the optimal control laws (maximum principle) where you have plugged in the approximate solution of the state and the adjoint variables. However, the approximation of the adjoint variables must be scaled, e.g. by the size of the stepsize or similarly. This is important!

If both control approximations coincide very accurately I would not go over to an indirect method, unless you really need more than 6-8 digits. For, the handling of an indirect method, such as multiple shooting, is by far not easy.

I hope this will help you. God luck!

Hans Josef

Dear Prof. Hans,

Thank you very much for your answer, it clarified few things to me.

BTW, would you recommend to use MATLAB functions/packages to solve the NLP, or C++ libraries are by far better than MATLAB?

I also was reading this paper by Christof Büskensa, , Helmut Maurerb

"SQP-methods for solving optimal control problems with control and state constraints: adjoint variables, sensitivity analysis and real-time control"

http://www.sciencedirect.com/science/article/pii/S0377042700003058

Do you recommend the methods used in this paper?

Thanks.

Dear Mohamed,

I would not make my own transcription method again, i.e. inventing the wheel again.

Please contact Bueskens or Gerdts for their software, they both are my former co-workers.

Best regards,

Hans Josef

Thanks Prof. Hans. I will contact them.

Dear Mohamed,

If you are familiar with Matlab this might be an option for you: Starting from the canonical system some efficient numerical algorithms (taking into consideration restrictions on both states and control) are implemented in the OCMat software tool developed by Dieter Grass (see, Grass, D., Caulkins, J.P., Feichtinger, G., Tragler, G., Behrens, D.A. (2008), Optimal Control of Nonlinear Processes. With Applications in Drugs, Corruption and Terror. Springer: Berlin, Heidelberg, New York), and you may even contact him via the ReseachGate :-).

Kind regards, Doris

Dear Doris, Dear Mohamed,

any kind of indirect methods suffers under the fact, that you need to know an initial guess for the adjoint variables. I have many many years of experience with the highly sofisticated multiple shooting codes by Oberle or Hiltmann. I consider them still of the best implemenatations available. If your problem is nonlinear --- and most of the interesting problems are highly nonlinear AND heavily restricted by inequality constraints, I am skeptic if you succeed in solving the problem in an acceptable time. Besides the guess for the adjoints you usually have to know the switching structure. Moreover, the underlying Newton method for solving the set of nonlinear equations has usually an extremely small domain of convergence. This requires the application of homotopy methods and this means time --- time ---- time.

Best regards,

Hans Josef

The usual method is to minimize squar of residuals between your final point in state space and the final conditions. It will be good to have an intelligent guess for the structure of the optimal solution. To handle free time you can or use the monotoneous

state variable instead of time (if you have one) or solve the problem for several final times and take the best. You also can use the DIDO MATLAB solver - it is rather cheap and works well.

You can try the conjugate gradient method algorithm

Thanks all for your help.

Dear Ilya Ioslovich,

Can you convert the DIDO code to C/C++ code or an executable file that can work on an embedded computer (e.g. gumstix) ?

You should ask Michael Ross who is the author and distruibutor of the toolbox.

Ilya

Dear Dear Mohamed,

I have done some works on optimal control problems.

I used the homotopy analysis method, homotopy perturbation methods, DTM and spectral homotopy analysis method for solving two-point boundary value problem (TPBVP), derived from Pontryagin’s maximum principle.

If you agree, I can help you.

Best regards

H. Saberi Nik

Dear Hassan,

Thank you for your help. I am actually not familiar with these methods. However, I am open to try different methods in order to evaluate the computational efficiency with relatively large scale models (12 states) and if they can be implemented in real time.

Dear Mohamed, after you apply any of the mentioned approaches based on the Pontryagins M. P., which are the first to try, you can also compare the results with a Direct approach. This consists in fully discretizing your problem to obtain a nonlinear optimization problem with constraints. In this case, the optimization will be made with respect to a big vector variable V=(X,U) where X and U are the state and control discretized vectors, respectively. Then you can apply any of the robust solvers for nonlinear optimization problems. There are many of them. I can confirm that the Sequential Quadratic approach (SQP) implemented in SNOPT by Gill, Murray and Saunders works good for nonlinear problems with different type of constraints.

Thanks Jorge. how can I get this SNOPT, by Gill? Do you have a link?

Thanks.

Yes, from Philip Gill's page at UCSD

http://cam.ucsd.edu/~peg/Software.html

you can get a limited free version of it. But I recommend you to first take a look on the documentation, that you will find on the same page, and check how it works. In particular, you should discretize your OCProblem and get a problem as the one called NP in the Introduction of the SNOPT documentation. Your cost function will become a function f, that depends on a variable x, which is nothing than the variable V=(X;U) that I mentioned above.

Edit: If the 300 degrees of freedom, allowed by SNOTP's free version, are not enough, you can try with SQPlab, from INRIA, which is also meant for discrete versions of Optimal Control Problems:

https://who.rocq.inria.fr/Jean-Charles.Gilbert/modulopt/optimization-routines/sqplab/sqplab.html

Although the producers of the solver are highly recognized scientists, I've never tried this package.

There is also an open source C++ package that implements pseudospectral methods called PSOPT:

http://www.psopt.org/

I have never tried it myself, though.

Thanks Jorge for the Edit, and thanks Roberto for your reply. I actually have seen PSOPT, but have not tried it yet.

Thanks all again.

I suggest that you see the book of Bete in optimal control, since it is included several numerical approaches to solve the control systems. Moreover you can use the Pseudo-spectral methods to solve control systems, numerically.

Thanks, Skandari.

Could you please provide a link?

Hi, for your optimal control problem you can use a number of methods. I will just list down a few that i have worked on.

Pseudospectral method - legendre, gauss, radue - refere to Anil V rao. you can also check the package GPOPS or DIDO

Shooting method

Model Predictive static programming - refer to Radhakant Padhi

LQR

State Dependent Riccati method

the list can go on.

But I think you should start with LQR first and then keep building on depending on your problem.

Thanks.

Hi there,

there are three families of numerical methods for OCP:

-indirect methods: the one Mohamed is searching for. They use variational methods and the Pontryagin PMP. As far as I know, they are implemented only by academics, see Bulirsh et al. or Bertolazzi et al. (XOptima, univ. Trento). They solve the OCP-associated Hamiltonian BVP, with some useful tools like homotopy/continuation.

- direct methods: they convert an OCP to a NLP and use standar optimization techniques. Some free software are ICLOCS (Imperial College), GPOPS (univ. Florida - which is no longer free actually). They are based on the NLP package IPOPT. There is also ACADO (univ. Leuven) which uses SQP and is written in C++.

- dynamic programming (DPP): they use the Hamilton-Jacobi-Bellman equation. You can look at the implementation by R.Luus, iterative dynamic programming.

Using software, remember the suggestion of prof. Pesch about the initial guess, because a good guess improves a lot the convergence.

Hi all,

Indeed, even though I agree with this segmentation, I would not say that indirect methods "use" variational methods, but rather that these methods try to find solutions that enforce the satisfaction of what is obtained with these principles (like PMP), that is the necessary conditions of optimality. 

What is also interesting with the direct methods is how an OCP can be converted into a classical NLP: (i) via discretization of both states and inputs - "the simultaneous approaches" or (ii) via discretization of the inputs only - "the sequential approaches",

Indeed, with the direct approaches one can use nearly any NLP solver ...

Prof. Skandar. Can you please give me the full details of  book by Bete in optimal control, the one you are referring there?

I suspect he means

John T. Betts - Practical Methods for Optimal Control Using Nonlinear Programming

http://books.google.ca/books/about/Practical_Methods_for_Optimal_Control_Us.html?id=Yn53JcYAeaoC

Thank you Prof.  Whidborne

Dear Mahammad

I suggest that you see the spectral methods for optimal control problems.

Thanks all, that is just a great amount of help. Indeed, I'll share my preferences later on, based on the implementations.

For those who are interested in numerical optimal control: there are a couple of practical examples with code in Matlab (though the explanations are in German)

http://www.tu-ilmenau.de/fileadmin/media/simulation/Lehre/Beispiele/OS2_Verfahren.pdf

Dear Mohammed,

Maple codes or conjugate gradient method will solve your problem. Fortran codes

could do same with high speed

Nwaeze E.

Dear Emmanuel,  

It's been long I have been expecting contribution in FORTRAN codes. As much as people are not looking at this area it makes more sense as programmer.  Having the code is not really important but ability to implement a small scale related problem few I'll. Bring more insight. I have a set of couples nonlinear odes which linearization approach is used to study the behavior and ultimately the stability of the network. 

The primary concern now is further treatment of nonlinear system in its nonlinear form and established a framework for comparing the linear and nonlinear form of the dynamic equation.  

I have the same family of problem that I am trying to solve.  In general if your system is having state and control constraints the indirect method (using pontryagin's minimum principle) will not work anymore. The reason is in order to use the indirect method, first you have to formulate the equivalent TPBVP. To formulate the TPBVP, you should be able to write the control explicitly as a function of state and co-states (which can be done only if dH/du =0, for constrained control system this is not true!). So the best option to try is to use direct method in which you first convert the optimal control problem to NLP( Nonlinear programming ) programmin

g and use some numerical methods (like multiple shouting method, or Collocation method.).  Personally, I am not that familiar with the NLP techniques but I am working on that right now. Hope this would give some direction.

Dear A. Kamil,

The nonlinear conjugate gradient  method (NCGM) handles such problems without linearization. Implementation of NCGM in FORTRAN CODES is quite simple if you are using PLATO coding environment. Thanks.

I have similar problem but  am using hamilton jacobi bellman. I was derive  some sets of matrix riccati differential equation with final condition and my state has initial initial condition. How do i get the optimal control u and optimal trajectories. 

Good day and a very happy moment to you. I will upload the file soon.

Emmanuel Nwaeze.

State Space?

Dear Mohamed Abdelkader,

You can find the following publications useful.

https://www.researchgate.net/publication/313335600_A_new_approach_based_on_using_Chebyshev_wavelets_for_solving_various_optimal_control_problems

https://www.researchgate.net/publication/312666126_State-control_parameterization_method_based_on_using_hybrid_functions_of_block-pulse_and_Legendre_polynomials_for_optimal_control_of_linear_time_delay_systems

https://www.researchgate.net/publication/290614049_A_Numerical_Approach_for_Solving_Optimal_Control_Problems_Using_the_Boubaker_Polynomials_Expansion_Scheme

https://www.researchgate.net/publication/265768743_Numerical_solution_of_nonlinear_optimal_control_problems_based_on_state_parametrization

https://www.researchgate.net/publication/257451558_Application_of_Chebyshev_polynomials_to_derive_efficient_algorithms_for_the_solution_of_optimal_control_problems

Article A new approach based on using Chebyshev wavelets for solving...

Article State-control parameterization method based on using hybrid ...

Article A Numerical Approach for Solving Optimal Control Problems Us...

Article Numerical solution of nonlinear optimal control problems bas...

Article Application of Chebyshev polynomials to derive efficient alg...

Pesudospectral methods are the best numerical and approximate methods to solve continuous optimization problems, specially optimal control problems. 

Can you send to me some papers on this subject?

There are many software packages that deal with this sort of problem; common ones include BOCOP, (Python) GEKKO, Tomlab, DIDO, CasADi, PROPT, etc. To solve your systems of ODEs (the state and adjoint equations), you could use a forward-backward Runge Kutta scheme (e.g. look at MATLAB's ODE45 solver). However, one must also be mindful of step errors due to variable-step solvers meeting a tolerance which is very small, alluding to a stiff system.