DARE cannot solve trivial problem (stuck in infinite loop)

[RussTedrake]

Calling DiscreteAlgebraicRiccatiEquation with

A = [ 0 , 1; 0, 0 ]
B = [ 0; 1 ]
Q = eye(2)
R = 1

results in the DARE solver getting stuck in an infinite loop in the reorder_eigen subroutine.

[RussTedrake]

fwiw - i suspect the right solution here is to fail early (since it's uncontrollable). i'm actually surprised that matlab's dlqr returns something (K = [0., 0.], S = diag([1., 2.]))

[weiqiao]

The bug is due to the incorrect assumption that the first generalized eigenvalue of (S,T) is always unstable. It will be fixed soon. The solution is P = diag([1,2]).

[RussTedrake]

this also falls into the infinite loop when A=B=Q=R=eye(2)

[weiqiao]

this also falls into the infinite loop when A=B=Q=R=eye(2)

You were not using the fixed version.

[RussTedrake]

Where is the fixed version? I’m running on master...

[weiqiao]

Where is the fixed version? I’m running on master...

The fixed version is here https://github.com/RobotLocomotion/drake/pull/8469

[miquelramirez]

Hi guys,

a brief heads up on this issue. The trivial test case proposed by @RussTedrake is still causing an infinite loop on master. Looking through the code, I think that the loop starting on line

https://github.com/RobotLocomotion/drake/blob/2d7b81fcdd80ce1370670d008d6d86e795a9edf3/math/discrete_algebraic_riccati_equation.cc#L315

is not correct. The problem is that whenever p == q either pointer do not get increased by block_size when they should (I think). A possible fix would be to replace the code in lines

https://github.com/RobotLocomotion/drake/blob/2d7b81fcdd80ce1370670d008d6d86e795a9edf3/math/discrete_algebraic_riccati_equation.cc#L338-L342

by

    if (p != q) {
      swap_block(S, T, Z, p, q, q_block_size);
    }
    p += q_block_size;
    q += q_block_size;

NOTE: Here I am assuming that reorder_eigen is a version of Kressner's pseudocode in page 60 of the book cited.

[hongkai-dai]

Resolved in #14865