EP1447727A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
System and method of accelerated active set search for quadratic programming in real-time model predictive control
Assignee: RTX Corp
•
Filing: 2004-02-16
•
Granted: —
•
Expires: 2024-02-16
Abstract
Abstract An active set algorithm exploits a 'hot start' for the set of binding constraints at optimality along with efficient linear algebra to make rapid progress tow ards the solution. The linear algebra is designed to deal with degenerate constraints as the required factorizations are performed and as degeneracy emerges, and not via a mostly unnecessary pre-process step. Combined together, these novel approaches enable solution of the control problem in real-time.
Inventors
- 👤 Indraneel Das
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-30 05:07
CPC Classifications
G; G05; G05B; G05B13/00; G05B13/02; G05B13/04; G05B13/048
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
155 words
A method for controlling a multivariable system including the steps of: a) receiving a plurality of sensor signals indicating current conditions of the
system; b) receiving a plurality of commands; c) determining a desired dynamic response of the system based upon the
commands and the sensor signals; d) in each of a plurality of time steps, formulating a problem of achieving the
desired dynamic response for a window spanning multiple time steps as a solution to
a quadratic programming problem; e) solving the quadratic programming problem in each time step using an
iterative algorithm which searches for an optimal active set; f) in each subsequent time step of the plurality of time steps, initializing a
search for the best active set based on a final active set of a prior time step of the
plurality of time steps; g) generating a plurality of actuator control commands based upon the
solution to the quadratic programming problem.
Claim 2
Dependent Claim
21 words
The method of claim 1 wherein the active set comprises a set of constraints
that are binding at an optimized solution.
Claim 3
Dependent Claim
23 words
The method of claim 2 wherein said step c) further includes the procedure of
dropping only one constraint with a negative Lagrange multiplier.
Claim 4
Dependent Claim
30 words
The method of claim 2 wherein said step c) further includes the procedure of
dropping all constraints that are not binding irrespective of signs of Lagrange
multipliers of the constraints.
Claim 5
Dependent Claim
42 words
The method of claim 2 further including the steps of: Determining that the final active set of the prior time step is not feasible in a
current timestep; Minimizing a weighted sum of the original QP problem and a measure of
infeasibility.
Claim 6
Dependent Claim
34 words
The method of claim 2 further including the steps of: Determining that the feasible point is largely inconsistent with the active set;
and Retaining inconsistent constraints in the active set while continuing the
optimization.
Claim 7
Dependent Claim
25 words
The method of claim 1 further including the step of performing a QR
factorization in each iterate of the iterative algorithm of said step e).
Claim 8
Dependent Claim
34 words
The method of claim 7 wherein a first iterate of the iterative algorithm
includes the step of performing a full QR factorization and subsequent iterates
include the step of performing a QR factorization update.
Claim 9
Dependent Claim
16 words
The method of claim 7 further including the step of detecting degeneracy
during each QR factorization.
Claim 10
Dependent Claim
14 words
The method of claim 9 further including the step of dropping a degenerate
constraint.
Claim 11
Dependent Claim
24 words
The method of claim 10 further including the step of detecting linear
dependency in the active constraints in each of the iterations without pre-processing.
Claim 12
Independent Claim
159 words
A method for controlling a multivariable system including the steps
of: a) receiving a plurality of sensor signals indicating current conditions of the
system; b) receiving a plurality of commands; c) determining a desired dynamic response of the system based upon the
commands and the sensor signals; d) in each of a plurality of time steps, formulating a problem of achieving the
desired dynamic response for a window spanning multiple time steps as a solution to
a quadratic programming problem; e) solving the quadratic programming problem in each time step using an
iterative algorithm; f) performing a Cholesky factorization of H in a first iteration; g) reusing the Cholesky factorization in iterations subsequent to the first
iteration; h) computing an unconstrained solution in one of the iterations; i) reusing the unconstrained solution in iterations subsequent to the one of
the iterations; and j) generating a plurality of actuator control commands based upon the
solution to the quadratic programming problem.
Claim 13
Dependent Claim
21 words
The method of claim 12 further including the step of performing a QR
factorization in each iterate of the iterative algorithm.
Claim 14
Dependent Claim
34 words
The method of claim 13 wherein an initial iterate of the iterative algorithm
includes the step of performing a full QR factorization and subsequent iterates
include the step of performing a QR factorization update.
Claim 15
Dependent Claim
16 words
The method of claim 13 further including the step of detecting degeneracy
during each QR factorization.
Claim 16
Dependent Claim
14 words
The method of claim 15 further including the step of dropping a degenerate
constraint.
Claim 17
Dependent Claim
24 words
The method of claim 16 further including the step of detecting linear
dependency in the active constraints in each of the iterations without pre-processing.
Claim 18
Independent Claim
225 words
A method for controlling a multivariable system including the steps of: a) receiving a plurality of sensor signals indicating current conditions of the
system; b) receiving a plurality of commands; c) determining a desired dynamic response of the system based upon the
commands and the sensor signals; d) in each of a plurality of time steps, formulating a problem of achieving the
desired dynamic response for a window spanning multiple time steps as a solution to
a quadratic programming problem; e) solving the quadratic programming problem in each time step using an
iterative algorithm, including iteratively solving a quadratic programming problem
where the set of indices of constraints in the active set is denoted by W and the rows
in the constraint matrix A corresponding to the active set are characterized by E , and
wherein a feasible point u f is known, Au f ≤ b , the method including the steps of: i) choosing an initial guess active set; ii) in iteration k , given a guess E for the active constraints, solving the Equality-Constrained
QP (EQP) s.t. Eu = r where r represents the sub-vector of right hand sides for the active
constraints; iii) determining the optimal u * , and Lagrange multipliers λ* as j) generating a plurality of actuator control commands based upon the
solution to the quadratic programming problem.
Claim 19
Dependent Claim
48 words
The method of claim 18 further including the steps of: Determining a largest α ∈ [0,1] such that u k -1 +α s is feasible, where s = u* - u k -1 ' u k -1 denotes the prior iterate and u 0 = u f .
Claim 20
Dependent Claim
10 words
The method of claim 19 where α is given by
Claim 21
Dependent Claim
21 words
The method of claim 20 further including the step of updating the guess for
the active set in the next iterate.
Claim 22
Dependent Claim
40 words
The method of claim 21 further including the step of adding to W the first
index i B corresponding to which α achieves its minimum value in the ratio test, the
guess for the active indices in the next iterate.
Claim 23
Dependent Claim
22 words
The method of claim 22 further including the step of dropping the constraint
with the most negative multiplier from the active set.
Claim 24
Dependent Claim
25 words
The method of claim 23 further including the step of: in the first iteration,
dropping all constraints that are not consistent if α < 1.
Claim 25
Dependent Claim
196 words
A model predictive control system comprising: a plurality of sensors for determining a state of the system and for generating
sensor signals indicative of the state of the system; a desired trajectory generator for creating a desired trajectory based upon the
plurality of sensor signals and a plurality of commands; a linearization module deriving a linearized model about the desired
trajectory; a quadratic programming module in each of a plurality of time steps
formulating a problem of achieving the desired trajectory for a multiple timestep
window as a solution to a quadratic programming problem; a quadratic programming solver for solving an optimization problem
established by the quadratic programming module to generate a profile of optimal
controls, the quadratic programming solver solving the quadratic programming
problem in each time step using an iterative algorithm which searches for an optimal
active set and in each subsequent time step of the plurality of time steps, initializing
a search for the best active set based on a final active set of a prior time step of the
plurality of time steps; and actuators acting on the system based upon the optimal controls to move the
system toward the desired trajectory.
Claim 26
Dependent Claim
21 words
The system of claim 25 wherein the active set comprises a set of constraints
that are binding at an optimized solution.
Claim 27
Dependent Claim
19 words
The system of claim 26 wherein the quadratic programming solver drops
only one constraint with a negative Lagrange multipliers.
Claim 28
Dependent Claim
26 words
The system of claim 26 wherein the quadratic programming solver drops all
constraints that are not binding irrespective of signs of Lagrange multipliers of the
constraints.
Claim 29
Dependent Claim
24 words
The system of claim 25 the quadratic programming solver performs a QR
factorization in each iterate of the iterative algorithm of said step e).
Claim 30
Dependent Claim
28 words
The system of claim 29 wherein a first iterate of the iterative algorithm
includes performing a full QR factorization and subsequent iterates include
performing a QR factorization update.
Claim 31
Dependent Claim
16 words
The system of claim 29 wherein the quadratic programming solver detects
degeneracy during each QR factorization.
Claim 32
Dependent Claim
14 words
The system of claim 31 wherein the quadratic programming solver drops a
degenerate constraint.
Claim 33
Dependent Claim
24 words
The system of claim 32 wherein the quadratic programming solver detects
linear dependency in the active constraints in each of the iterations without pre-processing.
Claim 34
Independent Claim
147 words
A method for controlling a multivariable system including the steps of: a) receiving a plurality of sensor signals indicating current conditions of the
system; b) receiving a plurality of commands; c) determining a desired dynamic response of the system based upon the
commands and the sensor signals; d) in each of a plurality of time steps, formulating a problem of achieving the
desired dynamic response for a window spanning multiple time steps as a solution to
a quadratic programming problem; e) optimizing a quadratic programming problem using an iterative algorithm
which searches for an optimal active set to solve the quadratic programming
problem, the algorithm including the steps of: i) Determining that an initial starting point set is not feasible; and ii) Reformulating the problem to obtain a feasible iterate. f) generating a plurality of actuator control commands based upon the
solution to the quadratic programming problem.
Claim 35
Dependent Claim
24 words
The method of claim 34 further including the step of minimizing a weighted
sum of the original QP problem and a measure of infeasibility.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.