[Title of Invention]

METHOD AND CONTROLLER FOR CONTROLLING OPERATION OF

MACHINE

[Technical Field]

[0001]

The present invention relates generally to automated process control, and more particularly to optimization-based receding horizon control of a machine tracking a trajectory.

[Background Art]

[0002]

Many advanced control techniques are formulated as optimization problems, which can be solved by mathematical programming. One class of such techniques is optimization-based receding horizon control, such as model predictive control (MPC). There are MPC formulations for both linear and nonlinear systems.

Nonlinear MPC solves nonlinear mathematical programs in real-time, which can be a challenging task due to a limitation on computing resources, the complexity of the problem to solve, or the time available to solve the problem. Therefore, most of the practical applications are based on a linearity assumption or approximation. The linear MPC typically-solves a -quadratic programming TpTobleh

[0003]

The MPC is based on an iterative, finite horizon optimization of a model of a machine and has the ability to anticipate future events to take appropriate control actions. This is achieved by optimizing the operation of the machine over a future finite time-horizon subject to constraints, and only implementing the control over the current timeslot. For example, the constraints can represent physical limitation of the machine, legitimate and safety limitations on the operation of the machine, and performance limitations on a trajectory. A control strategy for the machine is admissible when the motion generated by the machine for such a control strategy satisfies all the constraints. For example, at time t the current state of the machine is sampled and an admissible cost minimizing control strategy is determined for a relatively short time horizon in the future. Specifically, an online or on-the-fly calculation determines a cost-minimizing control strategy until time t + T, Only the first step of the control strategy is implemented, then the state is sampled again and the calculations are repeated starting from the now current state, yielding a new control and new predicted state path. The prediction horizon keeps being shifted forward and for this reason MPC is also called receding horizon control.

[0004]

The MPC can be used to generate the actual trajectory of the motion of the machine based on a model of the machine and the desired reference trajectory by solving an optimal control problem over a finite future time horizon subject to various physical and specification constraints of the machine. The MPC aims for minimizing performance indices of the machine motion, such as the error between the reference and the actual motion of the machine, the machine energy

consumption, and the induced machine vibration.

[0005]

However,_due_to the reeeding-horizon -and tracking nature of th^foblem, the MPC has no guarantee of finding an admissible solution. Specifically, the existence of the solution on a certain window of data (horizon) does not by itself guaranty that when the data window is shifted, a solution still exists. Thus, the control that is optimal for one iteration at one time period can place the machine in the state that forces the machine to violate some constraints during the next iteration, see, e.g., a method described in U.S. Patent 7,376,472

[0006] To address this problem, the conventional solutions either determine the optimal trajectory off-line to allow the time to verify the trajectory, or determine a suboptimal, but feasible trajectory as an input to the optimization method, or increase a length of the finite future time horizon to reduce the uncertainty of the optimization, see, e.g., Mayne et al.: "Constrained model predictive control:

Stability and optimality." Automatica, Volume 36, Issue 6, Pages 789-814, June 2000.

[0007]

However, in a number of applications, it is not possible to determine the feasible trajectory off-line. In addition, the increase of the finite future time horizon makes the computation more difficult, which can prevent the computation of the control strategy to be completed in the time allowed for the MPC method. Also, for longer time horizon, the future information required to determine the feasible trajectory might not be available.

[0008]

Some conventional methods guarantee admissibility with respect to certain tracking performance metrics only at the steady state operation of the controlled machine. For example, Pannocchia: "Disturbance models for offset - free model predictive control,"AIChE Journal (2003), 49(2), 426-437, Maeder et al.: "Linear offset-free model predictive control," Automatica (2009), 45(10), 2214-2222, describe control methods that guarantee tracking a reference trajectory at a steady state. Also, Ferramosca et al.: "MPC for tracking of constrained nonlinear systems," CDC/CCC 2009 and Falugi et al.: "Tracking performance of model predictive control," in Decision and Control (CDC), 2012 IEEE 51st Annual Conference on (pp. 2631-2636) describe methods that modify the reference trajectory to satisfy constraints on the machine dynamics.

[0009] All these methods fail to guarantee any performance metrics of the tracking of the trajectory during the transient phase of the operation. However, the transient response of a machine to a change from equilibrium is important for a number of applications, such as factory automation and automotive or aerospace vehicle controls. It is believed, that currently there is no method in the art that can guarantee the feasibility of tracking performance metrics of the machine tracking the trajectory in the transient stage.

[Summary of Invention]

[0010]

It is an objective of some embodiments of the invention to provide a system and a method for controlling a constrained operation of a machine according to a reference trajectory. It is another objective to provide such a system and a method that guarantees that at any moment of the controlling there is a control input resulting in the feasible state of the machine satisfying the constraints of the operation for all possible variations of the reference trajectory. It is another objective of some embodiments to provide such a system and a method that guarantees satisfaction of the constraints during transient stage of the operation of the machine.

[0011]

Various embodiments of the invention transform the tracking problem into an optimization problem subject to constraints. For example, some embodiments of the invention are based on a realization that a transient of the reference trajectory can be constrained, e.g., based on specification of the machine. Such realization allows limiting unpredictability of the transient stage of operation. In addition, the constraints on the transient of the reference trajectory can reduce the need for determining the reference trajectory in advance, which can be advantageous for some controller with limited computation capabilities. Some embodiments use only a model of the reference motion profile, but the model includes uncertainty, which represents all possible variations of the reference trajectory.

[0012]

Some embodiments of the invention are based on another realization that in some applications, it is important to guarantee that the tracking error is bounded within some predefined bounds, although the tracking error needs not be zero. In those applications, the tracking of the reference trajectory can also be represented as a constraint to be satisfied.

[0013]

The constraints of the machine, constraints on the transient of the reference trajectory and constraints on bounds of a tracking error form a feasible region of a state of the machine and a state of the reference trajectory. Accordingly, it is possible to optimize the control maintaining the state of the machine and the state of the reference trajectory within that feasible region and, thus, to convert the tracking problem into purely optimization problem.

[0014]

Due to the nature of optimization-based receding horizon control, the existence of a solution for a certain horizon does not by itself guarantees the existence of the solution for a subsequent horizon. However, some embodiments of the invention are based on yet another realization that it is possible to select a subset of the feasible region, such that from any state of the machine and of the reference trajectory within that subset, there is a control maintaining the state of the machine within the subset. Accordingly, if a cost function representing the operation of the machine is optimized subject to constraints defined by that special subset of the feasible region, as contrasted with the optimization within the feasible region itself, there is a guarantee that the resulting optimal trajectory tracks the reference trajectory with the bounded error and is always feasible. [0015]

Accordingly, one embodiment discloses a method for controlling an operation of a machine according to a model of a reference trajectory. The method includes determining a feasible region for states of the machine and states of the reference trajectory defined by constraints of the machine, constraints on a reference trajectory and constraints on bounds of a tracking error; selecting a subset of the feasible region, such that for any state of the machine and any state of the reference trajectory within the subset, there is an admissible control

maintaining the state of the machine within the subset for all admissible future states of the reference trajectory determined by the model and the constraints of the reference trajectory; and selecting an admissible control action for controlling the operation such that the state of the machine remains in the subset for all admissible future states of the reference trajectory.

[0016]

Another embodiment discloses a controller for controlling an operation of a machine according to a reference trajectory by selecting a control action for controlling the operation such that a state of the machine for all admissible future states of the reference trajectory remains in a subset of the feasible region of states of the machine and states of the reference trajectory, wherein the feasible region is defined by constraints of the machine, constraints on the reference trajectory and constraints on bounds of a tracking error of the reference trajectory, and wherein the subset of the feasible region is a control invariant, such that for any state of the machine within the subset, there is a control maintaining the state of the machine within the subset for all admissible future states of the reference trajectory.

[0017]

Yet another embodiment discloses a method for controlling an operation of a machine including determining a current state of the machine and a current state of the reference trajectory; selecting a control action from a plurality of admissible control actions that changes the current state of the machine into a next state of the machine such that the next state is within a control invariant subset for all admissible future states of the reference trajectory; and applying the control action to the machine.

[Brief Description of the Drawings]

[0018]

[Fig. 1]

Figure 1 is a block diagram of a controller and machine according to embodiments of the invention.

[Fig. 2]

Figure 2 is a block diagram of the controller according to embodiments of the invention.

[Fig. 3]

Figure 3 is a timing diagram of machine motions according to embodiments of the invention.

[Fig. 4]

Figure 4 is a diagram of a model of the reference trajectory and constraints on a transient of the reference trajectory according to embodiments of the invention.

[Fig. 5]

Figure 5 is an example of a two-dimensional projection of the feasible region form by various constraints according to embodiments of the invention. [Fig. 6]

Figure 6 is a block diagram of a method for controlling an operation of a machine according to a model of a reference trajectory in accordance with one embodiment of the invention. [Fig. 7]

Figure 7 is a block diagram of a method for determining a control invariant subset according to one embodiment of the invention.

[Fig. 8]

Figure 8 is a block diagram of a test according to one embodiment of the invention for verifying whether a polyhedral candidate subset is the control invariant.

[Fig. 9]

Figure 9 is a schematic of some principles behind the determination of the control invariant subset according to one embodiment of the invention.

[Fig. 10]

Figure 10 is a diagram of a method for selecting the control invariant subset by performing iteratively a backward-reachable region computation according to one embodiment of the invention.

[Fig. 11]

Figure 11 is a block diagram of an alternative method that determines the control invariant set.

[Fig. 12]

Figure 12 is a schematic of an effect of the method of Figure 11 with respect to the method of Figure 10.

[Fig. 13]

Figure 13 is a block diagram of a control method according to one

embodiment of the invention.

[Fig. 14]

Figure 14 is a block diagram of a control method according to another embodiment of the invention.

[Fig. 15] Figure 15 is a block diagram of a method according to some embodiments when only a value of a state of the reference trajectory at the current time step is known.

[Fig. 16 A]

Figure 16A is a block diagram of a method that uses the control invariant subset according to some embodiments of the invention.

[Fig. 16B]

Figures 16B is a block diagram of a method that uses the control invariant subset according to some embodiments of the invention.

[Description of Embodiments]

[0019]

Some embodiments of the invention provide a system and a method for controlling an operation of a machine according to a model of a reference

trajectory. Some embodiments control the machine using an optimization-based receding horizon control subject to constraints that guarantees the feasibility of tracking the reference trajectory with an error defined by bounds of a tracking error. A non-limited example of the receding horizon control is a model predictive control (MPC).

[0020]

Fig. 1 shows an example machine 120 connected to controller 110, e.g., the MPC controller, according to some embodiments of the invention. The controller 110 is programmed according to a model 102 of the machine. The model can be a set of equations representing changes of a state 121 and output 103 of the machine 120 over time as functions of current and previous inputs 11 1 and previous outputs 103. The model can include constraints 104 that represent physical and operational limitations of the machine. One embodiment expresses the model 102 as a linear difference equation x(k+ \) = Ax(k) +Bu(k)

y(k) = Cx(k) ^ ^

where A: is a time instant when the signals are sampled, u is the machine input, y is the machine output, x is the state of the machine, and A, B, C, are parameters of the model of the machine.

[0021]

During the operation, the controller receives a command d 101 indicating the reference behavior of the machine. The command can be, for example, a motion command. In response to receiving the command 101, the controller generates input u 1 1 1 for the machine. In response to the input, the machine updates the output y 103 and the state x 121 of the machine.

[0022]

The machine, as referred herein, is any device that can be controlled by certain manipulation input signals (inputs), possibly associated to physical quantities such as voltages, pressures, forces, and to return some controlled output signals (outputs), possibly associated to physical quantities such as currents, flows, velocities, positions. The output values are related in part to previous machine output values, and in part to previous and current input values. The dependency of previous inputs and previous outputs is encoded in the machine state. The operation of the machine, e.g., a motion of the machine, can include a sequence of output values generated by the machine following the application of certain input values.

[0023]

The reference operation of the machine according to the reference trajectory is the planned operation of the machine. Such operation, however, may not exactly be realizable due to physical and specification constraints. The tracking error of the machine is a measure of the difference between the reference operation of the machine and the actual operation obtained by applying a certain input to the machine.

[0024]

A model for the machine operation is a set of equations that describe how the machine outputs change over time as functions of current and previous inputs, and previous outputs. The state of the machine is any set of information, in general time varying, for instance an appropriate subset of current and past inputs and outputs, that, together with a model of the machine and future inputs, can uniquely define the future motion of the machine.

[0025]

The machine can be subject to physical and specification constraints limiting the range where the outputs, the inputs, and also possibly the states of the machine are allowed to operate.

[0026]

The controller is hardware or a software program executed in a processor, e.g., a microprocessor, which at fixed or variable period sampling intervals receives the machine outputs and the reference operation of the machine motion, and determines, using this information, the inputs for operating the machine.

[0027]

Fig. 2 shows a block diagram of the controller 110 according one

embodiment of the invention. The controller 110 includes a processor 201 connected to a memory 202 for storing the model 102 and the constraints 104, such as constraints of the machine, e.g., physical and specification constraints, constraints on a transient of the reference trajectory and constraints on bounds of a tracking error. For example, the constraints on the transient of the reference trajectory can include a possible type of changes of the state of the reference trajectory, rates of the change of the state of the reference trajectory among others. The bounds of the tracking error can include the allowed difference between a function the state of the machine and a function of the state of the reference trajectory. The function can be, e.g., identity function, linear combination, etc.

[0028]

The controller actuates the machine so that the machine output follows a reference d, 101, which is the output generated by a reference model that represents the reference trajectory of the machine

r{k + 1) = A _r r(k) + B _r y{k),

d(k) = C _r r(k\ (2) where r is a reference state of the reference model and r is a reference output of the reference model, /is the reference input, and A _T , B _r , C _r , are the parameters that define the model of the reference trajectory.

[0029]

In some embodiments, the model of the reference trajectory includes uncertainty, which is modeled without knowing precisely the value of reference input γ. As opposed to the machine input u, the reference input γ is not assigned by the controller by some external entities, such as a human operator or high level supervisory software. The reference input is a modification of the current state of the reference trajectory. The controller selects the machine input u in reaction to the reference input γ _> but cannot change the reference input γ.

[0030]

The machine is subject to constraints that describe physical and operational limits, which can be expressed by the set of linear inequalities

x(k) e X, u(k) e U, \/k≥0 , (3) where X, U are polyhedral set of states and inputs that define the admissible states and inputs, respectively, via linear inequality constraints. For example, a polyhedral set can be represented by linear inequalities, e.g.,

X = {x: Hx≤ K}.

[0031]

Checking if a point belongs to the set can be achieved by verifying the linear inequalities for the point, i.e.,

x(k £ X <= Hx(k)≤ K.

[0032]

An admissible state of the machine is a state x that satisfies the constraints of the state of the machine, e.g., as described in Equation (3). An admissible control of the machine is an input u that satisfies the input constraints, e.g., as described in Equation (3). An admissible trajectory of the machine whose model is described, e.g., by Equations (1) and (3) is a sequence of admissible states of the machine (x(0), x(\), x(i), x(i+l),...) where each state of the machine x(k+l) is related to the previous state x(k) by Equation (1) for an admissible input u{k). Given a machine state x ₀ the admissible future states of the machine are all the states of the machine jci such that there exists an admissible trajectory of the machine that starts at x ₀ and ends at x^.

[0033]

Some embodiments of the invention are based on a realization that the transient of the reference trajectory can be constrained, e.g., based on specification of the machine. Such realization allows limiting unpredictability of the transient stage of operation. In addition, the constraints on the transient of the reference trajectory can reduce the need for determining the reference trajectory in advance, which can be advantageous for some controller with limited computation resources.

[0034]

Some embodiments use only a model of the reference motion profile, wherein

r(k) e R, r(k) e Y, \/k≥0 , (4)

wherein R and / ^" are polyhedral sets that define the admissible values of the reference state and of the reference input, respectively. In this case the constraints in Equation (4) are satisfied by the reference generated by the model in Equation

(2).

[0035]

An admissible state of the reference trajectory is a reference state r that satisfies the constraints of the state of the reference trajectory, e.g., as described in Equation (4). An admissible input of the reference trajectory is an input ^that satisfies the input constraints of the reference trajectory, e.g., as described in Equation (4). An admissible trajectory of the reference whose model is described by, e.g., Equations (2) and (4) is a sequence of admissible states of the reference (r(0),r(l), ..., r(i), r(i+l),...) where each state of the reference trajectory r(k+\) is related to the previous state r(k) by Equation (2) for an admissible input of the reference trajectory y k). Given a reference trajectory state r ₀ the admissible future states of the reference trajectory are all the states of the reference trajectory r _x such that there exists an admissible trajectory of the reference that starts at r ₀ and ends at r

[0036]

Fig. 3 shows a timing diagram of the operation, e.g., motions, of the machine 120 according to some embodiments of the invention. The controller 1 10 generates the input 1 1 1 for the machine to perform the reference operation while enforcing the constraints using the expected machine behavior according to the model. The controller at each time k 301, solves a finite time optimal control problem for a prediction interval 304, e.g., from the current time till the Nnext times. The constraints can include constraints of the machine including regions of feasible 302 and feasible input 303.

[0037]

Some embodiments of the invention are based on another realization that in some applications, it is important to guarantee that the tracking error is bounded within the predefined bounds, although the tracking error needs not be zero. In those applications, the tracking of the reference trajectory can also be represented as a constraint to be satisfied. In those embodiments, the constraints also include constraints on bounds 310 and 312 of a tracking error between the reference trajectory 101 and the actual trajectory. In one embodiment constraints on bounds of a tracking error include

wherein ε is the allowed tracking error bound.

[0038]

Some embodiments of the invention are based on a realization that the transient of the reference trajectory can be constrained, e.g., based on specification of the machine. Such realization allows limiting unpredictability of the transient stage of operation. In addition, the constraints on transient of the reference trajectory can reduce the need for determining the reference trajectory in advance, which can be advantageous for some controller with limited computation capabilities.

[0039]

For example, although Equation (5) has to be satisfied at any point of time, some embodiments have knowledge of the future values of the reference motion r only along a limited future horizon. The reference motion needs to satisfy Equation (2) and Equation (4), but can be unknown. [0040]

Fig. 4 shows a diagram of the uncertainty of the model of the reference trajectory and the constraints on the transient of the reference trajectory. For example, for some iterations, such as a current iteration at a current time 410 for a prediction horizon 415, the reference trajectory 420 can be known. But for some other iterations, e.g., for a next iteration at a time 430 for a next prediction horizon 435, the reference trajectory at a step 425 may not be known.

[0041]

The model of the reference trajectory constrains a range 440 of possible future reference motions, thus providing the constraints on transients of the reference trajectory. The constraints can be determined in advance, but also can vary in dependence to previously determined trajectory. For example, the constraints on the reference trajectory at a specific time can be determined by a region 450. However, when the trajectory is determined at a step 425, the constraints on the reference trajectory can be tightened to a region 455. Thus, at the specific iteration, the region 455 defines the constraints on the reference trajectory.

[0042]

The constraints on the state of the machine, constraints on the reference trajectory and the constraints on bounds of a tracking error form a feasible region of a state of the machine and a state of the reference trajectory. Accordingly, it is possible to optimize the control maintaining the state of the machine and the state of the reference trajectory within that feasible region and, thus, to convert the tracking problem into a purely optimization problem.

[0043]

Fig. 5 shows an example of a two-dimensional projection of the feasible region 510 defined by various constraints according to embodiments of the invention. Typically, the feasible region is a multi-dimensional polytope determined by hyperplanes, which are represented by linear inequalities, along multiple dimensions corresponding to the constraints in Equations (3) and (4).

[0044]

Due to the nature of receding horizon control, the existence of a solution for a certain horizon does not by itself guarantees the existence of the solution for a subsequent horizon. For example, the state of the machine and a state of the reference trajectory 520 can be optimal and feasible for one iteration, but all control actions 521-524 that controller is allowed to take during the next iteration can bring a state of the machine outside of the feasible region 510.

[0045]

Some embodiments of the invention are based on yet another realization that it is possible to select a subset 515 of the feasible region, such that from any state of the machine within that subset, there is a control action maintaining the state of the machine within the subset for the known future states of the reference

trajectory or for all admissible future states of the reference trajectory. For example, for any state such as a state 530 within the subset 515 and within all possible control actions 531-534 that the controller can execute, there is at least one control action 534 that maintains the state of the machine and reference within the subset 515.

[0046]

Accordingly, if a control action for controlling the operation is selected such that the state of the machine remains in that special subset 515 of the feasible region, and the feasible region is generated also according to Equation (5), then there is a guarantee that the resulting optimal trajectory tracks the reference trajectory with the bounded error and every future state of the machine always admits at least one feasible control action. In this case, the subset 515 is a control invariant set. For example, the selection of the control action can be performed by optimizing a cost function representing the operation of the machine subject to constraints defined by that special subset 515 of the feasible region, as contrasted with the optimization within the feasible region 510 itself.

[0047]

Fig. 6 shows a block diagram of a method for controlling an operation of a machine according to a model of a reference trajectory in accordance with some embodiments of the invention. The method can be executed by a processor 601 of the controller 110.

[0048]

The method determines 610 a feasible region 510 of a state of the machine and a state of the reference trajectory defined by constraints 104 including constraints of the machine, constraints on transient of the reference trajectory and constraints on bounds of a tracking error. Next, the method selects 620 a subset 515 of the feasible region, such that from any state of the machine within the subset, there is a control maintaining the state of the machine within the subset and selects 630 a control action 640 for controlling the operation such that the state of the machine remains in the subset. In one embodiment, the selecting includes optimizing a cost function 635 representing the operation of the machine subject to constraints defined by the subset region 515. The cost function is optimized iteratively for a fixed time horizon to produce a control action 640 of a current iteration.

[0049]

In some embodiments, all steps of the method of Figure 6 are executed during the operation of the machine. In alternative embodiments, the steps 610, 620 are executed before the machine operation, and the cost function 635 or other principles of the selection of the control action are also defined before machine operation. Such operations can be executed either in a microprocessor or in a general purpose computing machine, such as a desktop computer, laptop, or engineering workstation. The results of step 620 and the cost function 635 are programmed in the memory of the microprocessor 110, and the step 630 is the only step that is repeatedly executed during operation of the machine.

[0050]

Determining Subsets of Feasible Space Based on Control Invariance Principles

Some embodiments determine the set 515 as a control invariant set for the machine model (1) and reference model (2) subject to constraints (3), (4). In some variations, when the reference input γ is unknown, the set 515 is a control invariant set for the machine of Equations (l)-(2) subject to constraints given by Equations (3)-(4) for disturbances /in the set Γ of the reference inputs.

[0051]

Figure 7 shows a block diagram of a method for determining the set 515 according to one embodiment. The method generates 710 a number of candidate sets as subsets of the feasible region 510. A candidate subset 720 is selected from the feasible region, and tested 730 to verify whether the candidate subset is a control invariant. If yes 733, the candidate subset is selected as the subset 515 and the methods terminates. Otherwise, if another candidate subset is available 740, the next candidate subset is selected and the test is repeated. Otherwise 750, new candidates are generated 710.

[0052]

Figure 8 shows a block diagram of a test according to one embodiment of the invention for verifying whether a polyhedral candidate subset 720 is control invariant. The method computes 810 the vertices of the polyhedron candidate set 720 and computes 820 the vertices of polyhedral set Γ 825 of the reference inputs. Then, a vertex of the candidate set is selected 830, and checked 840 whether there exists a control action u such that for every vertex of Γ the constraints in Equations (3), (4), (5) are satisfied. This step can be implemented by search or mathematical programming. If such control action u cannot be found, then the set is not control invariant 845. If such control action can be found and there are no more vertices to be checked 850, then the set is robust control invariant 855. Otherwise, the next vertex is selected.

[0053]

However, the generation and verification of candidate sets can take a significant amount of time, and one embodiment uses an automated procedure to generate and verify the candidate sets.

[0054]

Because the subset 515 is a control invariant set, a method for control invariant set computation can be used for generating the set 515. Such a method can be modified with the capability of enforcing constraints in Equation. (5) and considering the input γ to the model of the reference (2) as source of uncertainty.

[0055]

Figure 9 illustrates the principles behind the determination of the subset 515 according to one embodiment of the invention. The feasible set 510 of the state of the machine state and the state of the reference trajectory is

[0056]

The state of the machine 902 and the state of the reference trajectory 903 define a point in (x,r) 901 in the feasible region 510. Given the admissible set 904 for future states of the reference trajectory according to

C _r (r) = { _r . A _r r ₊ B e R} _{? (?)} the future state of the machine and the future state of the reference trajectory can be anywhere in the polyhedron 907, delimited by segments 905, 906. Thus, the controller can take any control action such that the future state of the machine 902 remains in the segment 910, so that the combination of the future machine state and future reference state remains in the polyhedron 907.

[0057]

If the set 907 is such that there is always a control action that keeps the machine state and reference state 901 in in the set 907 for the entire admissible range of the reference 904

Q _{x r}

it is always possible to guarantee

[(Ax +Buy (A _r r+ B _r r) ^< Y e C _X!r which guarantees that the constraints on the machine and on the tracking error bounds are satisfied. Notably, this procedure can be repeated at a next step because the update states are still inside Cx _if ., hence recursively guaranteeing the constraints enforcement.

[0058]

Figure 10 shows a diagram of a method for selecting the subset C _* ,,. by performing iteratively a backward-reachable region computation until a

termination condition is satisfied. The backward-reachable region computation removes all states from the current feasible region for which there is no control that maintains the state of the machine within the feasible region for reference trajectories satisfying the constraints on the transient of the reference trajectory.

[0059]

For example, the backward-reachable region computation initializes 1001 at a step k = 0 a current feasible region 1001 as the feasible region 510, Ω ₀ = {[*V] 6 ^ }

then determines 1002 a backward-reachable region of the states of the machine and reference trajectory that can be transition to the current feasible region for all the value of the admissible reference input according to

Ω _Μ = Pre(Q _t) C _y (r)) = {[xV] e X _{x r} : 3u e U, (Ax + Bu,A _r r + B _r r) e Q„V/ e C _r (r)}

■ (9)

[0060]

The computation of Equation (9) removes the states of the backward reachable region for which there exists no control action that keeps states into the current feasible region for all the admissible values of the future state of the reference.

[0061]

At step 1003 the computation tests if the backward-reachable region is equal to the current feasible region, i.e., Ω _ω == Ω^. If yes 1004, the backward-reachable region is control invariant 515 and the computation stops. Otherwise 1005, the backward-reachable region is used as current feasible region in the next iteration (k = k + 1) of the computation.

[0062]

The backward-reachable region computation of Figure 10 returns the largest existing control invariant set. However, because the set of admissible reference inputs is state dependent, the control invariant set is not a single convex

polyhedron but a set of convex polyhedra, which makes the use of such subset in a real time control difficult. Also, the backward-reachable region computation of Figure 10 can take significant amount of time (days, weeks, months).

[0063]

Figure 11 shows a block diagram of an alternative method that determines a control invariant set which is slightly smaller than the largest subset, but is a single convex polyhedron. Also, the method of Figure 1 1 is much faster, e.g., can determined the control invariant subset within minutes and/or hours.

[0064]

The method initializes 1101 the matrices M, L, and the sets F, X, as

k = 0, M ₀ = C, LQ = C _R , F ₀ = {e: | |e| | < e}, X ₀ = X and the current feasible region

Ω ₀ = {[xV] e X _{x r} r e C", (Cx- C _r r) e ₀ )}

[0065]

Initially, the current feasible region is the feasible region. The method is performed iteratively, such that the states that cannot be maintained in the current feasible region for all the admissible values of the future disturbance are removed , thus forming a new current feasible region. The current feasible region is reformulated 1 102 as polyhedral invariant subset of feasible region, in details as an intersection of a set of the states of the machine satisfying the constraints of the machine, the set of states on the trajectory satisfying some constraints on the transient of the reference trajectory, and the set of the states satisfying the error bounds constraints, such that a forward set /¾ in the form

Ω, = {[xV] e X _v : r e C, ^∞ ,x e X, {M _k x -L _k r) e F _k ]

: r e C _r

is obtained, where the constraints describe the maximum output admissible set for the reference trajectory state, that is the largest set of reference trajectory states for which the reference state admits input for which all the constraints (3) are satisfied. To that end, checking the constraints on the state of the machine and the constraints on the state of the reference trajectory are decoupled and the full range of reference input allowing the reference trajectory to move from an admissible state, regardless if the future state of the reference trajectory is admissible, is accepted.

[0066]

Then, the tightened backward-reachable region is determined 1103 according to

* _i = j[xV]€ X _{x r} : 3u€ U,r e C ^™ ,Ax+Bu e X _k , (M _k (Ax+Bu)-L _k (A _r r+B _r y)) e F _k , Vy e Γ} [0067]

If the tightened backward-reachable region equals 1104 the current feasible region, i.e.,

¾ ₊ i— ⁼ ¾ then 1 105 the tightened backward-reachable region is control invariant 515 and the algorithm stops with

[0068]

Otherwise 1106, the matrices M, L are updated as

M _k+1 = M _k A, L _{k+ 1} = L _k A _r

and 1 107 the sets F, X are updated as

Xk+i = i ^{x e χ} · ^' Ax + Bu E X _k ]

F _k +i = {v: 3u E U, 3b E F _k , v = b - M _k Bu + h _k B _r y, y e Γ}.

Then, the tightened backward-reachable region is assigned as new current feasible region 1 108, and a new iteration is performed from 1 102 with k=k+\ .

[0069]

Because in the method of Figure 1 1 the variable γ is now independent of the variable r, the resulting set C _{x r} is a polytope. [0070]

Figure 12 shows an effect of the method of Figure 11 with respect to the method of Figure 10. Because the dependence of the reference input γ on the reference state r is ignored, the subset 1201 obtained by the method of Figure 11 is smaller than the set 1202 obtained by the method of Figure 10, but the subset 1201 is a single convex polyhedron, while the subset 1202 includes a larger convex polyhedron 1203 and multiple smaller convex polyhedral 1204 at the borders, the union of which is not convex.

[0071]

Tracking Control with Guaranteed Feasibility

Some embodiments of the invention select the control action by optimizing a cost function representing the operation of the machine subject to constraints defined by the control invariant subset of the feasible region, which has been computed using a model of the machine, a model of the reference trajectory, a current state of the machine, and a current state of the reference trajectory.

[0072]

For cost functions that are linear or quadratic, the resulting problem can be efficiently solved by linear or quadratic programming possibly including integer variables. After the subset 515 is determined, different finite horizon problems for the control strategy are implemented by different embodiments tepending on available amount of future information on the reference.

[0073]

Figure 13 shows a block diagram of a control method according an embodiment, in which the values of the reference system state r are available for the entire prediction horizon, but not available afterwards. At any control cycle, the machine state and the future references along the future prediction horizon are acquired 1301, and the finite horizon optimal control problem is solved 1302. [0074]

In one embodiment, the optimizing is based on future states of the reference trajectory along a prediction horizon. In this embodiment, the solution 1302 includes determining states of the reference trajectory along a prediction horizon using the current reference state and the current reference input subject to constraints on the transient of the reference trajectory, constraints of the feasible region for all the steps of the prediction horizon except for the last one, and constraints of the subset of the feasible region for the last step of the prediction horizon.

[0075]

Additionally or alternatively, the solution 1302 can be according to

™η _«( * ₊ ολ..., _Β (* ₊ Λτ- _ΐ) ^F (x(k + N), r(k r(k + i), u(k + i))

s.t. Eqn (2),

(x(k + i), r(k + ) e X _x , i = 1, ... , N - 1

(x(k + N), r(k + N)) C _{x r}

u(k + i) e U, i = 0, ..., N- l

Given x(k), r (k), r(k + 1), r (k + 2), ...r (k + N).

[0076]

The first element of the optimal input solution u*(k) is applied 1303 to the machine, and, then, the controller waits 1304 for the next control cycle when the sequence is repeated.

[0077]

Figure 14 shows a block diagram of a method according an embodiment when only the current value of the reference state r and the current value of /are known. In this embodiment, the optimizing is based on a current reference state and a reference input and includes determining states of the reference trajectory along a prediction horizon using the current reference state and the current reference input. The determining is subject to constraints on the transient of the reference trajectory, constraints of the feasible region for a first step of the prediction horizon and constraints of the subset of the feasible region for remaining steps of the prediction horizon.

[0078]

For example, one embodiment acquires 1401 the state of the machine and determines the next value of the state r of the reference trajectory from the current value of the state r of the reference trajectory and the current value of the input γ using the reference model that represents the reference trajectory of the machine, e.g., as in Equation (2). The step 1402 produces a guess of the following values of the state r by selecting the reference input ^such that the state r satisfies the constraints in Equation (2)

r{k + i) e C _r ^∞ .

[0079]

The step 1403 is executed, and the finite horizon optimal control problem solved is ^F ( ^x ( ^k + ^N )> ^r ( ^k + ^N )) +∑ + 0, * + 0, k + ^/ )) s.t. Eqn (2),

(x(k + i), r(k + i)) <≡C _{x r} ,i = l, ..., N

u(k + i) e U, i = 0, ..., N- \

Given x(k), r(k), r(k + Y), r(k + 2),...r(k + N),

where the feasible subset region constraint is now used at all steps because the future value of the reference is guessed. Next, the first element of the optimal input solution u*(k) is applied 1404 to the machine, and, then, the controller waits 1405 for the next control cycle when the sequence is repeated.

[0080] Figure 15 shows a block diagram of a method according an embodiment when only the value of the reference state r at the current time step is known. The method acquires 1501 the machine states and determines 1502 all the future reference system states (including the immediate next one) by selecting such that by the reference state r of a model of Equation (2) satisfies the constraints

r(k + i) E C _r ^∞ .

[0081]

The method solves 1503 the time optimal control problem

F(x(k + N), r(k + N)) + q(x(k + i), r(k + i),u(k + / ^' )) s.t. Eqn (2),

(x(k + / ^' ), r(k + i), u(k + i)) e C _x ^ _u ,i = 0,..., N - l

u{k + i) e U, i = 0,..., N - l

Given x(k), r(k), r(k + 1), r(k + 2), ...r(k + N),

where the set

Cx.r.u = {x, r, u {Ax + Bu, A _r r + Β _ν γ) G C _{x r} , /y: A _r r + B _r y G C _r ^∞ ] (10) is the set of feasible machine states, feasible reference trajectory states and feasible machine inputs such that is the feasible machine input is applied to the feasible machine state, for all the future reference trajectory states generated by the feasible reference trajectory state and all the admissible reference inputs, the next machine state and reference state is in the subset 515 and hence satisfies constraints in Equations (3), (5). Such set (10) is directly computed from the control invariant subset 515. Next, the first element of the optimal input solution u*(k) is applied 1504 to the machine, and, then, the controller waits 1505 for the next control cycle when the sequence is repeated.

[0082]

Some embodiments are based on a realization that if the cost function is linear or convex quadratic, then if the subset 515 is determined using backward- reachable region computation of Figure 10, the optimization problems are mixed- integer linear or quadratic programming problems. This because the subset is the union of polyhedra, and the belonging of a vector v to a union of polyhedra

Xi = {x-. HiX≤ Ki}, i = 1, ... , i _p can be enforced by the mixed integer constraints

H _i v≤K _i + M(l - S _i ) _t i = l _l ... , n _p

^ e {0,l}, i = 1 n _p , y ^nV S _i ≥ l that once embedded in the optimization problem make it mixed-integer.

[0083]

The mixed integer programs are time consuming to solve and hence can be solved only for very short prediction horizon N. However, if the method of Figure 11 is used to determine 515, then the set is convex and the problems to be solved are linear or quadratic programming problems, which can be solved very fast even for long horizons N.

[0084]

Control using Pre-Existing Control Functions and Control Invariant Sets

Some embodiments are based on a recognition that it is unnecessary to obtain the optimal solution of the linear or quadratic programming problems or the mixed integer linear or quadratic programming problems. Any feasible solution of the problem formulated according the principles of the invention guarantees that all the future constraints are satisfied. This because any future state that is in the invariant set is guaranteed to be feasible and to allow for feasible solutions to be found in the future.

[0085]

For example, a control input that enforce the system constraints and the tracking performance can be obtained from a set of pre-existing control functions designed without considering the constraints (3) (5), that select the control action u given the state of the machine x and a state of the reference by using the set C _x>rM in Equation. (10) as control function selection rule. The examples of the control functions include acceleration and deceleration of the machine. The example of the control action for a specific control function can include a specific value of the acceleration or deceleration. Similar examples can be made for different machines, where the control functions include increase or decrease of voltage, position, force, etc.

[0086]

Figure 16A shows a block diagram of the selection method that uses the control invariant subset according to one embodiment. The embodiment

determines 1620 feasible states of the machine, feasible states of the reference trajectory and feasible inputs to the machine, such that is the feasible machine input is applied to the feasible machine state, for all the future reference trajectory states generated by the feasible reference trajectory state and all the admissible reference inputs, the next machine state and reference state remains in the feasible subset 515 which satisfies constraints in Equations (3), (5). Next, the control function generating the control action enforcing that the state of the machine is the feasible state of the machine, the state of the reference trajectory is the feasible state of the reference trajectory, and the input to the machine is the feasible input to the machine is selected 1630.

[0087]

Figure 16B shows an example of a method employing the principles of the method of Figure 16A. Given 1601 the pre-existing control functions and the set C _Vi „, at every control cycle 1602 the machine state and reference trajectory state are acquired, a candidate control function is selected 1603, and the candidate control action provided by the candidate control function is evaluated 1604. The control action is verified 1605 by checking whether the current state of the machine, the current state of the reference trajectory and the candidate control action belongs to the set C _{x r>u} . If the verification is positive, the command is applied 1606 to the machine. Otherwise 1607, if there are more candidate control functions to be selected a new candidate control function is selected, or an error is returned 1608.

[0088]

The above-described embodiments of the present invention can be

implemented in any of numerous ways. For example, the embodiments may be implemented using hardware, software or a combination thereof. When

implemented in software, the software code can be executed on any suitable processor or collection of processors, whether provided in a single computer or distributed among multiple computers. Such processors may be implemented as integrated circuits, with one or more processors in an integrated circuit component. Though, a processor may be implemented using circuitry in any suitable format.

[0089]

Also, the various methods or processes outlined herein may be coded as software that is executable on one or more processors that employ any one of a variety of operating systems or platforms. Additionally, such software may be written using any of a number of suitable programming languages and/or programming or scripting tools, and also may be compiled as executable machine language code or intermediate code that is executed on a framework or virtual machine. Typically the functionality of the program modules may be combined or distributed as desired in various embodiments.

[0090]

Also, the embodiments of the invention may be embodied as a method, of which an example has been provided. The acts performed as part of the method may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in an order different than illustrated, which may include performing some acts concurrently, even though shown as sequential acts in illustrative embodiments.