Kalman filter-based optimizer and method and optimizing
First Claim
1. Apparatus comprising:
- a filter having first and second input ports an output port, which filter develops at said output port an estimate of the state of a system whose observable output corresponds to the input signal applied to said first input port, and whose output matrix, which relates said observable output to the current state of said system, corresponds to the input signal to said second input port;
a combiner responsive to said output port of said filter, to a first input port of said apparatus, and to a second input port of said apparatus, where said first input port of said apparatus is adapted to receive a collection of signal elements representative of a matrix A, said second input port of said apparatus is adapted to receive a collection of signals representative of a vector c, and said combiner develops an output signal γ
that is proportional to c-AT w, where w is the signal at said output port of said filter, where AT is the transpose of of matrix A and AT w is the product of the matrix AT by the vector w;
a processor responsive to said outpput port of said filter, to said first input port of said apparatus, to said second input port of said apparatus, and to the signal γ
, for developing a replacement control signal candidate, x(k+1), based on said γ
, A, c, and a current control signal candidate, x(k), and for incrementing k, where k is an integer,means for developing a signal Dx(k), a signal Dx(k) c, and a signal AT Dx(k), where Dx(k) represents a diagonal matrix with the values of x(k) on the diagonal;
means for applying said Dx(k) c signal to said first input port of said filter, and said AT Dx(k) signal to said second input port of said filter; and
means for applying said x(k) signal to an output port of said apparatus.
1 Assignment
0 Petitions
Accused Products
Abstract
Making use of the conceptual and computational similarities between the Karmarkar method and the Kalman filter a controller system is capable of handling the observer function, the minimum time controller function and the minimum energy controller function. The system includes an element that has the computational structure of a Kalman filter. The inputs of this element are qualitatively controlled to deliver the desired results to the remaining computation elements. In a controller for an LP control task, the element develops the dual vector signal used in the affine scaling algorithm by applying information to it as if its task were to estimate the states of a system whose observable output is Dx(k) c, the input is O, the observation noise covariance matrix R is close to zero, the transition matrix is I and the matrix that describes the relationship between the measurable parameters and the observable output is AT Dx(k). Different controls applied to the Kalman filter structure element (and to the other elements of the system) yield control signals for QP control tasks.
-
Citations
12 Claims
-
1. Apparatus comprising:
-
a filter having first and second input ports an output port, which filter develops at said output port an estimate of the state of a system whose observable output corresponds to the input signal applied to said first input port, and whose output matrix, which relates said observable output to the current state of said system, corresponds to the input signal to said second input port; a combiner responsive to said output port of said filter, to a first input port of said apparatus, and to a second input port of said apparatus, where said first input port of said apparatus is adapted to receive a collection of signal elements representative of a matrix A, said second input port of said apparatus is adapted to receive a collection of signals representative of a vector c, and said combiner develops an output signal γ
that is proportional to c-AT w, where w is the signal at said output port of said filter, where AT is the transpose of of matrix A and AT w is the product of the matrix AT by the vector w;a processor responsive to said outpput port of said filter, to said first input port of said apparatus, to said second input port of said apparatus, and to the signal γ
, for developing a replacement control signal candidate, x(k+1), based on said γ
, A, c, and a current control signal candidate, x(k), and for incrementing k, where k is an integer,means for developing a signal Dx(k), a signal Dx(k) c, and a signal AT Dx(k), where Dx(k) represents a diagonal matrix with the values of x(k) on the diagonal; means for applying said Dx(k) c signal to said first input port of said filter, and said AT Dx(k) signal to said second input port of said filter; and means for applying said x(k) signal to an output port of said apparatus. - View Dependent Claims (2, 3, 4)
-
-
5. Apparatus for developing control signals to minimize the operational cost, cT x, of a given system, where c is a vector of cost coefficient signals for said given system, superscript T represents the transpose and x is a vector of controllable parameters of said given system which affect said operational cost, and where said given system is characterized by Ax=b, where A is a matrix of constraint signals and b is a vector of constraint limits, Comprising:
-
a processor for estimating a state w(k) of a second system, k being a repetition index, said processor having a first input port for applying to said processor observable outputs of said second system, a second input port for applying to said processor information relating said state of said second system to said observable outputs of said second system, with said processor receiving at said first input port signals that correspond to Dx(k) c, where Dx(k) is a diagonal matrix with the elements of a given vector x(k) on the diagonal, and receiving at said second input port signals that correspond to AT Dx(k), first means for combining said developed w(k) of said processor and said c, A, and Dx(k) to form a constant γ
signal;second means for combining said developed γ
signal, said x(k), Dx(k), c, and A to form a new given vector x(k) for a next repetition; andmeans for testing said state, w(k), developed by said processor to determine whether to inhibit said next repetition and apply the given vector x(k) that was last developed by said second means for combining to an output port of said apparatus. - View Dependent Claims (6, 7)
-
-
8. An arrangement comprising:
-
a physical enterprise characterized by an operational cost cT x, which enterprise operates under a set of constraints A and constraint limits b such that Ax=b, where c are cost coefficients, superscript T represents the transpose and x is a set of controllable parameters of said enterprise that interact with said coefficients to affect said operational cost; and a controller coupled to said enterprise for minimizing said operational cost, where said controller includes A. a processor for estimating a state w(k) of a system characterized by
space="preserve" listing-type="equation">z(t+1)=Fz(t)+Gu(t)+v(t)
space="preserve" listing-type="equation">y(t)=Hz(t)+e(t)where z(t) is a state vector of said system, F is a state transition matrix of said system, G is an input matrix of said system, H is an output matrix of said system, u(t) is a control input vector of said system, v(t) is a system noise of said system, y(t) is a measured output of said system, and e(t) is measurement noise of said system, where t is an iteration index of said processor and where said processor is arranged to receive a signal corresponding to AT Dx(k) for said output matrix H and a signal corresponding to Dx(k) c for said measured output y(t), to develop thereby a state estimate of said system corresponding to said vector w(k), where Dx(k) is a diagonal matrix with the elements of vector x(k) on the diagonal and x(k) is a given potential vector x of said enterprise, and k is an iteration index of said controller; B. means responsive to said w(k), said c and to said A to develop a constant γ and
select a constant α
between 0 and 1.0;C. means for combining said x(k), Dx(k), c, A, γ and
α
to form a new potential vector x(k) of said system;D. means for applying information about said new potential vector of said system, x(k), to said processor; E. means for testing said state vector w(k) developed by said processor to inhibit said means for applying so that said information is not applied to said processor, and to sending the last developed vector x(k) to said enterprise to control said operational cost of said enterprise, when a selected threshold is exceeded.
-
-
9. An observer/controller apparatus for developing control signals to minimize operational cost, cT x, of a given system, where c is a vector of cost coefficient signals for said given system, superscript T represents the transpose and x is a vector of controllable parameters of said given system which affect said operational cost, and where said given system is characterized by Ax=b, where A is a matrix of contraint signals and b is a vector of constraint limits, comprising:
-
an observer including a Kalman filter responsive to an observable output of a given system to develop an estimate of the operational state of said given system, and a controller responsive to said observer, wherein said controller includes a second Kalman filter for estimating the state, w, of a second system whose observable output which is applied to said second Kalman filter corresponds to Dz, and whose output matrix, which relates said state of said second system to said observable output of said second system is Dz AT, where Dz is a diagonal matrix with the elements of a vector z on the diagonal; means responsive to said w, said c and to said A to develope a constant γ and
a constant α
between 0 and 1.0;means for combining said z, Dz, c, A, γ and
α
to form a vector z'"'"';means for a) assigning z'"'"' to z, b) developing said observable output, and c) applying said observable output to said second Kalman filter; means for testing said state w developed by said second Kalman filter to determine when said means for applying should cease applying said observable output to said second Kalman filter and when said z'"'"' is assigned to said controllable parameters x; and means for transmitting said controllable parameters x to said given system.
-
-
10. Apparatus for developing control signals to minimize operational cost, 1/2xT Ω
- x-cT x, of a given system, where c is a vector of cost coefficient signals for said given system, superscript T represents the transpose and x is a vector of controllable parameters of said given system which affect said operational cost, Ω
is at least a semi-positive definite matrix, and where said given system is characterized by Ax=b, where A is a matrix of constraint signals and b is a vector of constraint limits, comprising;a processor for estimating a state w(k) of a second system, k being a repetition index, said processor having a first input port for applying to said processor observable outputs of said second system, a second input port for applying to said processor information relating said state of said second system to said observable outputs of said second system, with said processor receiving at said first input port signals that correspond to Dx(k) c, where Dx(k) is a diagonal matrix with the elements of a given vector x(k) on the diagonal, and receiving at said second input port signals that correspond to (AL)T Dx(k), where L is such that LLT =(Ω
+Dx(k)-2),means for combining said developed w(k) of said processor and said c, A, Ω
, and Dx(k) to form a constant γ
signal;means for combining said developed γ
signal, said x(k), Dx(k), c, and A to form a new given vector x(k) for a next repetition; andmeans for testing said state, w(k), developed by said processor to determine whether to inhibit said next repetition and apply the given vector x(k) that was last developed by said means for combining to an output port of said apparatus.
- x-cT x, of a given system, where c is a vector of cost coefficient signals for said given system, superscript T represents the transpose and x is a vector of controllable parameters of said given system which affect said operational cost, Ω
-
11. A method for controlling a physical system to reduce operational costs of said system, as measured by the cost function cT x, where c is a vector of cost coefficients, superscript T represents the transpose and x is a vector that represents the controllable parameter values of said system, which method includes the steps of
A) receiving signals representative of the characteristics of said system that provide a measure of constraint relationships A that must be satisfied within said system in relation to constraint limits b that are applicable to said system, B) developing a control signals vector x based on said received characteristics of the system by iteratively developing a candidate control signals vector x(k), k being the iteration index, through the iterative steps 1) developing a dual vector w(k), 2) computing a scalar multiplier γ - responsive to the developed dual vector,
3) developing a new candidate for vector x, x(k+1), that corresponds to x(k) modified in accordance with said dual vector w(k) and scalar multiplier γ
, and
4) incrementing k and returning to step 1 when the primary termination test
space="preserve" listing-type="equation">(c-A.sup.T w(k))≧
0
space="preserve" listing-type="equation">and
space="preserve" listing-type="equation">x(k)·
(c-A.sup.T w(k))≧
0fails, and assigning the last-developed x(k+1) signals vector to said x signals vector and proceeding to step C when said primary termination test does not fail, and C) applying said x signals vector to control inputs of said system, The improvement comprises initializing an iteration index t to 1, a covariance measure P(0/0) to mI, where m is a large positive real value and I is the identity matrix, and a state estimate z(0/0) to a preselected value, and developing said dual vector w(k) by carrying out the computation steps of; Computing a Kalman gain matrix
space="preserve" listing-type="equation">K(t)=P(t-1/t-1)H.sup.T (HP(t-1/t-1)H.sup.T +η
I).sup.-1,developing an estimate of a filtered state
space="preserve" listing-type="equation">Z(t/t)=Z(t-1/t-1)+K(t)[D.sub.x(k) c-Hz(t-1/t-1)]where H=AT Dx(k), developing an updated value of the covariance measure
space="preserve" listing-type="equation">P(t/t)=[I-K(t)P(t-1/t-1)and incrementing t and returning to said computing of a Kalman gain matrix when a secondary termination test is not met, and assigning the last developed z (t/t) to said dual vector w(k) when said secondary termination test is met, said secondary termination test being met when the expected value of [Dx(k) c-Hz(t-1/t-1)] is 0 and the expected value of [Dx(k) c-Hz(t-1/t-1)·
z(t/t)] is 0.
- responsive to the developed dual vector,
-
12. A method for controlling a physical system to reduce operational costs of said system, as measured by the cost function cT x, where c is a vector of cost coefficients, superscript T represents the transpose and x is a vector that represents the controllable parameter values of said system, which method includes the steps of
A) receiving signals representative of the characteristics of said system that provide a measure of constraint relationships A that must be satisfied within said system in relation to constraint limits b that are applicable to said system, B) developing a control signals vector x based on said received characteristics of the system by iteratively developing a candidate control signals vector x(k), k being the iteration index, through the iterative steps ofdeveloping a dual vector signal w(k) corresponding to (ADx(k)2 AT)-1 ADx(k)2 c where, Dx(k) is a diagonal matrix with the values of x(k) on the diagonal, developing a constant γ- that corresponds to ##EQU13## where ei is the unit vector,
3) developing a new candidate for vector x, x(k+1), that corresponds to ##EQU14## where α
is a selected constant greater than 0 and less than 1, and ) incrementing k and returning to step 1 when the primary termination test
space="preserve" listing-type="equation">(c-A.sup.T w(k))≧
0
space="preserve" listing-type="equation">and
space="preserve" listing-type="equation">x(k)·
(c-A.sup.T w(k))≧
0fails, and assigning the last-developed x(k+1) signals vector to said x signals vector and proceeding to step C when said primary termination test does not fail, and C) applying said x signals vector to control inputs of said system, the improvement comprises initializing an iteration index t to 1, a covariance measure P(0/0) to mI, where m is a large positive real value and I is the identity matrix, and a state estimate z(0/0) to a preselected value, and developing said dual vector w(k) by carrying out the computation steps of; Computing a Kalman gain matrix
space="preserve" listing-type="equation">K(t)=P(t-1/t-1)H.sup.T (HP(t-1/t-1)H.sup.T +η
I).sup.-1,developing an estimate of a filtered state
space="preserve" listing-type="equation">z(t/t)=z(t-1/t-1)+K(t)[D.sub.x(k) c-Hz(t-1/t-1)]where H=AT Dx(k), developing an updated value of the covariance measure
space="preserve" listing-type="equation">P(t/t)=[I-K(t)H]P(t-1/t-1)and incrementing t and returning to said computing of a Kalman gain matrix when a secondary termination test is not met, and assigning the last developed z(t/t) to said dual vector w(k) when said secondary termination test is met, said secondary termination test being met when the expected value of [Dx(k) c-Hz(t-1/t-1)] is 0 and the expected value of [Dx(k) c-Hz(t-1/t-1)·
z(t/t)] is 0.
- that corresponds to ##EQU13## where ei is the unit vector,
Specification