Kalman filter-based optimizer and method and optimizing

• US 5,115,391 A
• Filed: 01/26/1990
• Issued: 05/19/1992
• Est. Priority Date: 01/26/1990
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Puthenpura, Sarat C., Sinha, Lakshman P.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Gordon, Paul
• Application Number:
  US07/471,175
• Time in Patent Office: 844 Days
• Field of Search: 364/148, 364/152, 364/153, 364/154, 364/164, 364/165, 364/402
• US Class Current: 700/32
• CPC Class Codes: G05B 13/02 electric

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 D_x(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 A^T D_x(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.

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-A^T w, where w is the signal at said output port of said filter, where A^T is the transpose of of matrix A and A^T w is the product of the matrix A^T 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 D_x(k), a signal D_x(k) c, and a signal A^T D_x(k), where D_x(k) represents a diagonal matrix with the values of x(k) on the diagonal;

means for applying said D_x(k) c signal to said first input port of said filter, and said A^T D_x(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.

2. The apparatus of claim 1, further comprising a controllable system whose operational costs are controlled through a set of control signals applied to control ports of said controllable system, having said control ports of said controllable system responsive to said x(k) signal developed at said output port of said apparatus, with the A matrix input signal applied to said apparatus set to correspond to a set of constraint coefficients under which said controllable system operates, and the c input signal applied to said apparatus set to correspond to cost coefficients applicable to said operational costs of said controllable system.

3. The apparatus of claim 2, further comprising an observer system responsive to observable outputs of said controllable system for determining the values of said A input signal.

4. The apparatus of claim 1 wherein said filter further comprises a third filter input to which is applied covariance information pertaining to a measurement noise in measuring said observable output of said system.

5. Apparatus for developing control signals to minimize the operational cost, c^T 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 D_x(k) c, where D_x(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 A^T D_x(k),

first means for combining said developed w(k) of said processor and said c, A, and D_x(k) to form a constant γ

signal;

second means for combining said developed γ

signal, said x(k), D_x(k), c, and A to form a new given vector x(k) for a next repetition; and

means 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.

6. The method of claim 5 wherein said new given vector x(k) for the next iteration, that is x(k+1), is developed in accordance with the expression ##EQU11## where α

is a selected constant greater than 0 and less than 1.

7. The method of claim 5 wherein said γ

signal is developed in accordance with the expression ##EQU12## where e_i is the unit vector and where i is an integer that designates a particular element in vector e_i.

8. An arrangement comprising:

a physical enterprise characterized by an operational cost c^T 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 A^T D_x(k) for said output matrix H and a signal corresponding to D_x(k) c for said measured output y(t), to develop thereby a state estimate of said system corresponding to said vector w(k), where D_x(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), D_x(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, c^T 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 D_z, and whose output matrix, which relates said state of said second system to said observable output of said second system is D_z A^T, where D_z 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, D_z, 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/2x^T Ω

x-c^T 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 D_x(k) c, where D_x(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 D_x(k), where L is such that LL^T =(Ω

+D_x(k)^-2),

means for combining said developed w(k) of said processor and said c, A, Ω

, and D_x(k) to form a constant γ

signal;

means for combining said developed γ

signal, said x(k), D_x(k), c, and A to form a new given vector x(k) for a next repetition; and

means 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.

11. A method for controlling a physical system to reduce operational costs of said system, as measured by the cost function c^T 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))≧

0

fails, 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=A^T D_x(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 [D_x(k) c-Hz(t-1/t-1)] is 0 and the expected value of [D_x(k) c-Hz(t-1/t-1)·

z(t/t)] is 0.

12. A method for controlling a physical system to reduce operational costs of said system, as measured by the cost function c^T 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 (AD_x(k)² A^T)^-1 AD_x(k)² c where, D_x(k) is a diagonal matrix with the values of x(k) on the diagonal,

developing a constant γ

that corresponds to ##EQU13## where e_i 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))≧

0

fails, 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=A^T D_x(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 [D_x(k) c-Hz(t-1/t-1)] is 0 and the expected value of [D_x(k) c-Hz(t-1/t-1)·

z(t/t)] is 0.