Method and system for computing reference signals for machines with redundant positioning

Abstract

A method computes reference signals for a machine with redundant positioning by first generating a reference trajectory according to an ordered list of points. Then, using a filter or by choosing the value of the reference at each sampling time, a reference trajectory for the slow subsystem is produced. Next, determine whether the reference trajectory and the slow subsystem reference trajectory violate feasibility constraints, and if true, slowing down the reference trajectory and repeating with the generation of the slow subsystem reference trajectory. The slow subsystem reference trajectory is sent, via a model predictive control block, to a slow positioning subsystem controller, and a combination of the slow subsystem reference trajectory and the reference trajectory is sent to a fast positioning subsystem controller.

Claims

1. A method for computing a reference trajectory to position a machine that includes a slow positioning subsystem and a fast positioning subsytem, comprising the steps of: generating a reference trajectory according to an ordered list of points; producing a slow subsystem reference trajectory by either filtering the reference trajectory or chosing a value of the reference trajectory; determining whether the reference trajectory violates feasibility constraints by checking a recursive feasibility condition and a persistent tracking condition to determine whether the reference trajectory and the reference trajectory for the slow subsystem violate the feasibility constraints, wherein the checking for the recursive feasibility condition is performed by a forward reachability test; and if true; slowing down the reference trajectory and repeating the generating and determining steps; and otherwise sending the slow subsystem reference trajectory to the slow positioning subsystem; and sending a combination of the slow subsystem reference trajectory and the reference trajectory to the fast substem, wherein the steps are performed in a processor.

2. The method of claim 1, wherein the generating uses a trapezoidal profile for a velocity of sub-trajectories between two consecutive points.

3. The method of claim 2, where the trapezoidal profile is obtained by selecting an acceleration to be maximal until the velocity is within predetermined limits, then selecting an acceleration to be zero so that the velocity remains within the predetermined limits, and then selecting a deceleration to be maximal until the velocity is zero.

4. The method of claim 1, wherein the slow subsystem reference trajectory is generated using a filter.

5. The method of claim 4, wherein the filter is a zero phase finite impulse response filter, a zero phase infinite impulse response filter, or a low pass filter.

6. The method of claim 1, wherein the checking for the recursive feasibility condition is performed by verifying whether a state of the slow positioning system belongs to a maximal output admissible set.

7. The method of claim 1, wherein the forward reachability test is performed by verifying satisfaction of a set of linear inequalities.

8. The method of claim 6, wherein the forward reachability test is performed by verifying satisfaction of a set of linear inequalities.

9. The method of claim 1, wherein the checking for the persistent tracking is performed by checking whether minimal and maximal reference bounds are at a distance lesser than a stroke of the fast positioning subsystem from initial and final points of a current position of the slow positioning subsystem.

10. The method of claim 9, wherein the checking is performed by verifying satisfaction of linear inequalities involving maximal and minimal bounds, current and future terminal positions of the slow positioning subsystem and a stroke of the fast positioning subsystem.

11. The method of claim 1, wherein the slowing down reduces a maximal acceleration and a maximal velocity of the reference trajectory.

12. The method of claim 11, wherein the repeating maintains an iteration index, and a slowdown factor is a non-increasing function of the iteration index.

13. The method of claim 1, wherein the fast positioning subsystem always follows, within an error tolerance, a difference between the reference trajectory and the slow subsystem reference trajectory.

14. The method of claim 1, wherein the slow subsystem reference trajector is sent to the slow positioning subsystem via a model predictive control (MPC) module.

15. The method of claim 1, wherein the machine operates continuously while satisfying the feasibility constraints.

16. The method of claim 1, wherein the machine is a laser drilling system.

17. The method of claim 1, wherein the machine is a laser cutting system.

18. The method of claim 1, wherein the machine is a laser marking system.

19. The method of claim 1, wherein the machine is a scribing system.

20. The method of claim 1, wherein the machine is a laser direct imaging system.

21. The method of claim 1, wherein the machine is an electron beam processing machine.

22. A method for computing a reference trajectory to position a machine that includes a slow positioning subsystem and a fast positioning subsytem, comprising the steps of: generating a reference trajectory according to an ordered list of points; producing a slow subsystem reference trajectory by either filtering the reference trajectory or chosing a value of the reference trajectory; determining whether the reference trajectory violates feasibility constraints; and if true; slowing down the reference trajectory and repeating the generating and determining, wherein the slowing down reduces a maximal acceleration and a maximal velocity of the reference trajectory, and wherein the repeating maintains an iteration index, and a slowdown factor is a non-increasing function of the iteration index; and otherwise sending the slow subsystem reference trajectory to the slow positioning subsystem; and sending a combination of the slow subsystem reference trajectory and the reference trajectory to the fast substem, wherein the steps are performed in a processor.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram of a reference generator for a redundant positioning system according to embodiments of the invention;

(2) FIG. 2 is a schematic of a linear relationship of the position vectors for fast and slow positioning subsystems to reach the laser spot according to embodiments of the invention;

(3) FIG. 3A is a time history of a trajectory for laser spot according to embodiments of the invention;

(4) FIG. 3B is a time history for velocity and acceleration for a portion of the trajectory shown in FIG. 3A time according to embodiments of the invention;

(5) FIG. 4 is a schematic of steering the slow positioning subsystem to a next position and allowed tolerances in position and velocity according to embodiments of the invention;

(6) FIG. 5 is a schematic for checking for intersample tracking violations based on maximal and minimal bounds according to embodiments of the invention;

(7) FIG. 6A is a schematic of the reference trajectory according to embodiments of the invention;

(8) FIG. 6B is a schematic of adding a new portion to the reference trajectory according to embodiments of the invention;

(9) FIG. 6C is a schematic of determining a new filtered reference trajectory for the slow positioning subsystem using a filter according to embodiments of the invention;

(10) FIG. 6D is a schematic of the persistent tracking and recursive feasibility constraints for the newly added filtered reference trajectory for the slow positioning subsystem according to embodiments of the invention;

(11) FIG. 6E is a schematic of slowing down the reference trajectory such that the persistent tracking and recursive feasibility constraints become feasible according to embodiments of the invention; and

(12) FIG. 7 is a schematic of pseudo code for trajectory slowdown according to embodiments of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(13) As shown schematically in FIG. 1, the embodiments of the invention provide a system and method 100 for generating reference trajectories for positioning machines with redundant actuators, e.g., a laser drilling system. It is understood that the invention can be applied too other types of positioning systems with redundant actuators.

(14) In particular, we have described embodiments using a redundant laser drilling system, but the invention has the same effect for a processing machine such as a redundant laser cutting system, a redundant laser marking system, a redundant scribing system, a redundant laser direct imaging system or a redundant electron beam processing machine.

(15) The overall system includes the reference trajectory generator 100, a slow positioning subsystem 102 and a fast positioning subsystem 103. Depending on components selected, such as linear actuators and galvano mirror assemblies, the velocity of the fast positioning system is about one order of magnitude faster than the slow positioning subsystem, and the acceleration is at least three orders faster.

(16) The reference signal trajectory generator 100 includes trajectory generator 110, an optional filter 120, an infeasibility detector 130 for determining feasibility violations, which are all serially connected. A trajectory slowdown block 135 provides feedback to the trajectory generator. The filter can be, for example, a low pass zero-phase finite impulse response (FIR) filter, or a low pass zero-phase infinite impulse response (IIR) filter, or a low pass IIR filter. The infeasibility detector 130 can be implemented in hardware or a processor.

(17) The slow positioning subsystem 102 includes a model predictive control (MPC) module 140, a slow-axis control 150, and an X-Y table 151. Typically, the workpiece is mounted on the table. The fast subsystem includes a fast-axis controller 161 and galvano mirror assembly 161. In combination, the slow and fast subsystems position a laser spot relative to the workpiece on the table. In a system with flying optics, besides the mirror moving, the optical assembly is moved on the X-Y table, while the workpiece is stationary. In yet an alternative embodiment, the optical assembly (other than the mirror itself) is stationary, and the X-Y table and the workpiece are moved. The embodiments can be worked with either configuration.

(18) Operationally, the system receives an ordered list of points 101 as input, (X.sub.k, Y.sub.k) for k=1, 2, . . . , N, for the laser spot 170 on the workpiece. This list can be stored as in a non-volatile memory. The trajectory generator 110 takes this list as input and generates a reference trajectory 111 as output. The reference trajectory 111 is a function of time for the X and Y coordinates of the points between each of the successive elements of the ordered list 101. The reference trajectory 111 for the X-axis and Y-axis is generated as shown in FIG. 3A, A velocity profile 303 for a portion 302 of the trajectory is shown in FIG. 3B.

(19) The optional filter 120 takes the reference trajectory 111 and produces a filtered reference trajectory 112 for the slow positioning subsystem 102. Alternatively, one can choose a value of the reference trajectory to generate a slow subsystem reference trajectory 113.

(20) The infeasibility detector 130 checks the feasibility of the filtered reference trajectory or the slow subsystem reference trajectory. If there is a possibility of a constraint violation, then the trajectory slowdown block 135 slows down the reference trajectory 111 by reducing its maximal acceleration and maximal velocity and feeds the reduced maximal acceleration and velocity back to the trajectory generator 110 to regenerate the reference trajectory 111. This process repeats until a feasible filtered reference trajectory or a feasible slow subsystem reference trajectory results so that the machine can operate such that the constraints are satisfied.

(21) After a feasible filtered reference trajectory 112 or slow subsystem reference trajectory 113 for the slow positioning subsystem is generated, the filtered reference trajectory or the slow subsystem reference trajectory 113 is fed to the model predictive control (MPC) module 140. The MPC is a control approach that solves a receding horizon optimal control problem. It has the capability to directly enforce system constraints. It also has the capability to generate a smooth trajectory to avoid mechanical vibrations. The MPC 140 output is sent to the slow-axis controller 150 to position the X-Y table (or galvano mirror assembly) relative to the workpiece, by either moving the table or the galvano mirror assembly, depending on the configuration of the machine.

(22) In the fast positioning subsystem, the MPC output is also subtracted 145 from the reference trajectory 111 and sent to the fast-axis controller 160 for the galvano mirror 161. In this way the entire machine trajectory, i.e., the laser spot 170, is a function of the fast positioning subsystem and the slow positioning subsystem trajectories e.g.,
x.sub.laser spot=f.sub.x(x.sub.fast,x.sub.slow)
y.sub.laser spot=f.sub.y(y.sub.fast,y.sub.slow)

(23) In some embodiments, the relationship between the laser spot position and the positions of the fast and slow positioning subsystems can be approximated using a linear function.

(24) The method and system can be performed in a processor connected to memory and input/output interfaces by busses as known in the art. The method can be run in real time.

(25) Of particular interest are the infeasibility detector 130, and the trajectory slowdown 135 blocks. The combination of these two blocks guarantees that a feasible filtered reference trajectory for the slow positioning subsystem (or slow subsystem reference trajectory) is passed to MPC block 140. This means that the machine is operated such that the reference trajectory is always within the range of motion of the fast positioning subsystem, and other constraints and limitations are satisfied.

(26) As shown in FIG. 2, the reference trajectory 111 is approximated as a linear combination of the vectors {right arrow over (r)} for fast and slow positioning subsystems.

(27) As shown in FIG. 3A, and assuming an ordered list of points 101 for the laser spot on the workpiece, a portion 301 of the reference trajectory 111 in FIG. 1, or 601 in FIG. 6A is a function of time for the X and Y axis and is constructed by connecting together a series of sub-trajectories 302 between two consecutive X-Y elements, (p.sub.n(1) and p.sub.n(2), of the ordered list 101. The subscript indexes the points, and the numbers in bracket are 1 and 2 for the x and y coordinates, respectively.

(28) As shown in FIG. 3B, a trapezoidal velocity profile 303 is used to generate sub-trajectories 302 between the two consecutive points.

(29) During acceleration phase 304 of the sub-trajectory the maximal acceleration is applied, while during the coasting period 305 the acceleration is set to zero. The maximal deceleration rate is then used during the deceleration period 306 until the laser spot reaches the target position with a zero velocity. At the end of the sub-trajectory 302, when the laser spot reaches the target position, the laser spot stops for a dwell time, e.g., to drill a hole in the workpiece.

(30) The distance between the two consecutive positions of the ordered list of positions 101 determines whether or not the maximal velocity limit is reached on the way to the target position. To compute the times t.sub.1 to t.sub.4, the shortest distance at which the maximal velocity is reached is computed according to

(31) $\begin{array}{cc}\mathrm{pitch}=\frac{v_{\max }^2}{a_{\max }}.& \left(1\right)\end{array}$

(32) Depending on the pitch and the distance between the two consecutive positions of the ordered list of positions 101, the time indices t.sub.1 to t.sub.4 can be computed according to the following set of equations (2)

(33) $\{\begin{array}{cc}{t}_1=t_2=\sqrt{\frac{\mathrm{distance}}{a_{\max }}}& \mathrm{distance}\mathrm{pitch}\\ t_3=2\sqrt{\frac{\mathrm{distance}}{a_{\max }}}& \\ t_4=t_3+t_{\mathrm{dwell}}& \\ t_1=\frac{v_{\max }}{a_{\max }}& \mathrm{distance}>\mathrm{pitch}\\ t_2=t_1+\left(\frac{\mathrm{distance}}{v_{\max }}-\frac{v_{\max }}{a_{\max }}\right)& \\ t_3=t_2+t_1& \\ t_4=t_3+t_{\mathrm{dwell}}& \end{array}$

(34) For distances shorter than the pitch, the velocity profile has a triangular shape. Although, the X and Y actuators are not dynamically coupled, the fact that both coordinates coincide with the target position at the same time links the two coordinates. As a result, the distance used for the times t.sub.1 to t.sub.4 is computed as
distance=max{|P.sub.i+1(1)P.sub.i(1)|,|P.sub.i+1(2)P.sub.i(2)|},(3)
where P.sub.i and P.sub.i+1 represent the positions of two consecutive points from the ordered list of positions 101. The described trajectory generator 110 is designed for a laser drilling machine. In a laser cutting machine where the laser is always on, a different velocity profile may be used. Most significantly, the dwell time will be set to zero. The other blocks described hereafter will remain unchanged.

(35) We realize that in order to use the MPC 140 in the redundant laser drilling machine, the filtered reference trajectory 112 (or slow subsystem reference trajectory 113) and the reference trajectory 111 have to satisfy specific requirements as a result. When the filtered reference trajectory 112 (or slow subsystem reference trajectory 113) does not satisfy these specific requirements, the MPC 140 may fail to enforce all system constraints. This may cause the required position of the laser spot to fall outside of the stroke range of the fast positioning subsystem, resulting in tracking errors for the laser spot. We further realize that the feasibility of filtered reference trajectory 112 (and slow subsystem reference trajectory 113) can be verified by checking two main specifications; a recursive feasibility constraint, and a persistent tracking constraint, as described below in greater detail.

(36) To perform the task of checking the recursive feasibility constraint and the persistent tracking constraint, we start from an initial feasible portion of the filtered reference trajectory 112 (or slow subsystem reference trajectory 113). Based on this, we have to maintain the feasibility of the filtered reference trajectory (or slow subsystem reference trajectory) when the trajectory generator goes through a new cycle, that is, when a next portion of reference trajectory 111 needs to be generated.

(37) Given the predictive nature of the MPC 140, the filtered reference trajectory for the slow positioning subsystem (or slow subsystem reference trajectory) is generated for N steps in the future, i.e., the control horizon. As a result, when the system is at time step k1 the filtered trajectory or slow subsystem reference trajectory for the slow positioning subsystem has already been generated until the time step k+N1. Therefore, feasibility of the filtered trajectory or slow subsystem reference trajectory for the slow positioning subsystem has to be evaluated for the period k+N1 to k+N.

(38) Recursive Feasibility

(39) In what follows, system input refers to the command that is applied to the slow positioning subsystem of the machine and the system output is the resulting slow positioning subsystem position. Two types of embodiments are considered for this invention. In one embodiment, the command is the torque applied to the slow positioning subsystem. In the other embodiment, the command is the reference trajectory for the slow positioning subsystem. These different embodiments are described below.

(40) The term state refers to the smallest subset of time varying quantities such as positions and velocities of the machine such that by knowing the state at a certain time instant and the input into the positioning subsystem for an interval of time T into the future, the future behavior of the machine is known for that interval of time T.

(41) In some embodiments of this invention, the state variables are the position and velocity of the slow positioning subsystem, and the input is the torque applied to the slow positioning subsystem. Such embodiments can be represented by the following equation.
J+b{dot over (y)}=ku,(4)
where y is the generalized position of the slow positioning subsystem (usually either a linear position or a rotational position), J is the generalized inertia of the system, b is the damping, and k is the torque constant. In this equation, u is the applied torque. This system can be expressed in the following form,

(42) $\begin{array}{cc}\stackrel{.}{x}=\mathrm{Ax}+\mathrm{Bu}\mathrm{where}x=\left[\begin{array}{c}\mathrm{position}\\ \mathrm{velocity}\end{array}\right]\mathrm{and}u=\mathrm{torque}.& \left(5\right)\end{array}$

(43) In other embodiments, the input represents the desired slow positioning subsystem position, i.e., the reference trajectory for a servo controller actuating the slow positioning subsystem, and the states are the position and its derivatives up to (n1).sup.th order.

(44) $\begin{array}{cc}{a}_n\frac{{}^{n}y}{t^n}+\mathrm{.Math.}+a_1\stackrel{.}{y}+a_{0}y=u,& \left(6\right)\end{array}$
where y is again the generalized position of the slow positioning subsystem and u is the reference position of the slow positioning subsystem. Similarly, this system can be represented as
{dot over (x)}=Ax+Bu(7)
where

(45) $x={\left[\begin{array}{cccc}y& \stackrel{.}{y}& \mathrm{.Math.}& \frac{{}^{n-1}y}{t^{n-1}}\end{array}\right]}^T$
and u=reference position.
In equations (4) and (7), matrices A and B are the state and control matrices of appropriate dimensions.

(46) The recursive feasibility is commonly guaranteed by using a terminal equality constraint in applications of MPC where the reference trajectory is a constant value of time. However, the terminal equality constraint does not by itself guarantee the recursive feasibility of MPC, when the reference trajectory is time-varying.

(47) We realize that in order to maintain the recursive feasibility, in addition to the terminal equality constraint implemented in MPC 140, the reference trajectory for the slow positioning subsystem needs to satisfy the following forward reachability test:
x.sub.k+NReach(x.sub.k+N1)(8)
where x.sub.k+N is the vector of the filtered reference trajectory for the slow positioning subsystem (or slow subsystem reference trajectory) (position and velocity) at the time step k+N, and Reach(x.sub.k+N1) represents all feasible states that can be reached within one time step using an admissible control.

(48) For practicality purposes, the terminal equality constraint in MPC is usually implemented as a tight inequality (terminal set) constraint. This approach is understood by those skilled in the art, and is depicted in FIG. 4 where parameters .sub.pos and .sub.vel represent the allowed tolerances in position and velocity. Given the prespecified tolerances, x.sub.k+N1 represents a set of acceptable states surrounding x.sub.k+N1. The assumption that the problem was feasible at the previous time step (k+N1) means that
x.sub.k+N1|k1X.sub.k+N1,(9)
where x.sub.k+N1|k1 is the state prediction for the time step k+N1 performed at the time k1.

(49) Hence, as shown in FIG. 4, we need to compute an admissible control input that steers the slow positioning subsystem position 401 from any position in the set X.sub.k+N1 to a position in the set X.sub.k+N, while satisfying all state constraints. This constraint can be satisfied if and only if:
Pre(X.sub.k+N)X.sub.k+N1=X.sub.k+N1,(10),
where Pre(X.sub.k+N) is defined as the set of states that can be driven into the set X.sub.k+N in one time step while satisfying input and state constraints.

(50) Determining the Pre-set of a linear system is a computationally complex operation. It has been another realization of this invention that the satisfaction of the above constraint, Equation (10), can be determined by checking whether the system can be driven from all vertices of the set X.sub.k+N1 to any vertex of the set X.sub.k+N. This can be expressed as,
x.sub.iV.sub.X.sub.k+N1,x.sub.jV.sub.X.sub.k+N,s.t. x.sub.jAx.sub.iBU,(11)
where A and B are the state and control matrices representing the slow positioning subsystem dynamics, V.sub.X.sub.k+N is the set of vertices of X.sub.k+N, U is the set of admissible control inputs, and is a Minkowski sum.

(51) For each x.sub.iV.sub.X.sub.k+N1 and x.sub.jV.sub.X.sub.k+N, the condition in equation (11) can be transformed into a set of inequalities as follows,

(52) $\begin{array}{cc}\left[\begin{array}{c}{I}_{22}\\ -I_{22}\end{array}\right]\left(x_j\right)\left[\begin{array}{c}A\left(x_i\right)+{\mathrm{Bu}}_{\max }\\ -A\left(x_i\right)-{\mathrm{Bu}}_{\min }\end{array}\right],& \left(12\right)\end{array}$
where u.sub.max, u.sub.min represent the maximal and minimal admissible inputs.

(53) In a different embodiment of this invention, terminal equality constraint can be replaced by a terminal set constraint where an output admissible set (positive invariant set) can be used as a terminal set constraint. In this approach, an output admissible set (positive invariant set), O, is computed such that,

(54) $\begin{array}{cc}\left[\begin{array}{c}{x}_{k+N|k}\\ {\stackrel{\_}{y}}_{k+N}\end{array}\right]O.Math.\{{\begin{array}{c}{x}_{k+N|k}X\\ .Math.y_{k+N|k}-{\stackrel{\_}{y}}_{k+N}.Math.\end{array}}_{\mathrm{pas}},& \left(13\right)\end{array}$
where X is the set of admissible states, y.sub.k+N1 is the slow positioning subsystem position, and y.sub.k+N represents the filtered reference trajectory for the slow positioning subsystem (or slow subsystem reference trajectory) (position only) at the time step k+N. Maximal positive invariant sets O.sub. (the biggest invariant set that contains all possible invariant sets) can be computed by iterating over the backward reachable set computation until the sets computed in two consecutive iterations are equal. The procedure starts from a target set. The target set here is
.sub.0={x|xX,|x(1)y|.sub.pos},(14)
where x(1) is the first element of the slow positioning subsystem state vector (position). Starting from the target set (14), the set .sub.i+1 is calculated as Pre(.sub.i). The procedure continues until .sub.i+1=.sub.iO.sub.=.sub.i+1.

(55) Using the invariant nature of O.sub., the following set of linear inequalities can be used to verify whether the terminal constraint set can be satisfied.

(56) $\begin{array}{cc}\left[\begin{array}{c}{x}_{k+N-1|k}\\ {\stackrel{\_}{y}}_{k+N}\end{array}\right]O_{}.Math.H_x{x}_{k+N-1|k}+H_{\stackrel{\_}{y}}{\stackrel{\_}{y}}_{k+N}K,& \left(15\right)\end{array}$
where matrices H.sub.x, H.sub.y, and K are used to represent the invariant set as a series of half spaces.

(57) Persistent Tracking

(58) We also realize that in order to satisfy the stroke constraints of the fast positioning subsystem, the slow positioning subsystem must move in a manner that the reference trajectory 111 is always within the stroke range of the fast positioning subsystem. We refer to this requirement as a persistent tracking requirement. To describe this condition, we assume that the terminal equality (terminal set) constraint can be satisfied for the previous and the current time steps.

(59) Therefore, the last portion of the slow positioning subsystem trajectory is considered to be connecting position y.sub.k+N1 (the filtered reference trajectory for the slow positioning subsystem (or slow subsystem reference trajectory) at the time step k+N1) to y.sub.k+N (the filtered reference trajectory for the slow positioning subsystem (or slow subsystem reference trajectory) at the time step k+N). It should be noted that the slow positioning subsystem is assumed to be moving linearly between two consecutive positions.

(60) We realize that by using the motion of the slow positioning subsystem (between y.sub.k+N1 and y.sub.k+N) and a limit (d.sub.max,f) of the fast positioning subsystem stroke, an acceptable range of motion for the reference trajectory 111 can be found, where d.sub.max is the fast system stroke, and the subscript f represents the fast subsystem. Furthermore, we realize that due to the significant difference between the sample rates of the slow and the fast positioning subsystems, to ensure persistent tracking, the inter-sample locations of the reference trajectory 111 have to be considered. This means that the persistent tracking constraint cannot be guaranteed by checking the tracking limits only at the time steps k+N1 and k+N.

(61) As shown in FIG. 5, our solution to efficiently check for inter-sample tracking violations is based on determining the maximal and minimal bounds for the reference trajectory 111 during each time step of the slow positioning subsystem. As shown in FIG. 5, ref.sub.maxk+N (501) is the maximal value of the reference trajectory 111 between time step k+N1 and time step k+N. Similarly, ref.sub.mink+N (502) is the minimal value of the reference trajectory 111 between time step k+N1 and time step k+N. Using these bounds, the persistent tracking constraint can be expressed by the following four linear inequalities

(62) $\begin{array}{cc}\{\begin{array}{c}.Math.{\mathrm{ref}}_{\max k+N}-{\stackrel{\_}{y}}_{k-1+N}.Math.d_{\max ,f}\\ .Math.{\mathrm{ref}}_{\min k+N-}{\stackrel{\_}{y}}_{k-1+N}.Math.d_{\max ,f}\\ .Math.{\mathrm{ref}}_{\max k+N}-{\stackrel{\_}{y}}_{k+N}.Math.d_{\max ,f}\\ .Math.{\mathrm{ref}}_{\min k+N}-{\stackrel{\_}{y}}_{k+N}.Math.d_{\max ,f}\end{array}.& \left(16\right)\end{array}$

(63) Considering that the terminal equality constraint in the MPC 140 is implemented as a tight inequality constraint, each inequality in equation (16) is replaced with two inequalities, where, for example, y.sub.k1+N is once replaced with y.sub.k1+N+.sub.pos and another time with y.sub.k1+N.sub.pos.

(64) Procedure for Slowing Down the Trajectory

(65) As described above, we provide the necessary conditions for the filtered reference trajectory 112 (or slow subsystem reference trajectory 113), and as a result, reference trajectory 111 to guarantee the future feasibility of the MPC 140. Using these constraints, we realize that by checking for possible future constraint violations, the reference trajectory 111 can be automatically modified (slowed down) to guarantee constraint satisfaction.

(66) FIG. 7 shows the flowchart for the trajectory slowdown block 135. The trajectory slowdown block 135 modifies the reference trajectory 111 by reducing the maximal acceleration and the maximal velocity of the laser spot. In FIG. 7, M is the ratio of fast positioning subsystem frequency to the slow positioning subsystem frequency. The procedure first checks 710 for possible infeasibilities in the newly added reference trajectory for the slow positioning subsystem 112. If infeasibility in not detected, the procedure terminates. Otherwise, the maximal acceleration and maximal velocity are reduced 720 by a slowdown factor (f.sub.slowdown). The slowdown factor is a non-increasing function of the iteration index (i). One option is to use a constant value smaller than 1. To improve the convergence rate, variable slowdown factors can be used. One possibility is to specify the slowdown factor as a monotonically decreasing function of the iteration index (i), such as
f.sub.slowdown(i)=f.sub.slowdown(1).sup.i, where 0.9f.sub.slowdown(1)0.95.(17)

(67) It is also possible to select the slowdown factor from a precalculated vector of slowdown factors.

(68) 0$\begin{array}{cc}{f}_{\mathrm{slowdown}}\left(i\right)=\{\begin{array}{cc}{F}_{\mathrm{slowdown}}\left(i\right)& ip\\ F_{\mathrm{slowdown}}\left(p\right)& i>p\end{array}\mathrm{where}{F}_{\mathrm{slowdown}}=\left[\begin{array}{cccc}{f}_1& f_2& \mathrm{.Math.}& f_p\end{array}\right].& \left(18\right)\end{array}$

(69) Then, the trajectory generator 110 regenerates reference trajectory 111. This is followed by the optional filter 120 and infeasibility detector 130. This procedure 700 is continued until a next portion of feasible reference trajectory 111 and therefore a new filtered feasible reference trajectory for the slow positioning subsystem 112 (or slow subsystem reference trajectory 113) is generated.

(70) Combining the description of different blocks in FIG. 1, one complete cycle of the reference generator for redundant positioning system 100 is described below. The results of steps taken during each cycle are presented in FIGS. 6A-6E.

(71) It is worth mentioning that the sampling rate of the reference generator for redundant positioning system 100 is the same as the sampling rate of the slow-axis controller 150. In reference signal generator 100, the optional filter 120, the infeasibility detector 130, the trajectory slowdown 135, and the MPC 140 operate at the same sampling rate as the slow-axis controller 150. The trajectory generator 110, however, operates at a higher sampling rate equal to the sampling rate of the fast-axis controller 160. This results in reference trajectory 111 to have the same sampling rate as the fast-axis controller 160.

(72) For clarity and simplicity, an inset 610 in FIG. 6E shows the meaning of all curves in FIGS. 6A-6E. For example, the bold solid line represents the reference trajectory 111, and the cross symbol represents the filtered reference trajectory 112 (or slow subsystem reference trajectory 113) for the slow positioning subsystem 102.

(73) FIG. 6A shows the beginning of the time step k. During the previous time step (k1), the slow positioning subsystem has moved to a next position 601.

(74) FIG. 6B shows the next iteration is started by the trajectory generator 110 generating a next portion 602 of reference trajectory. The generated reference trajectory 602 covers one sampling period of the slow positioning subsystem from the time (k+N1)M+N.sub.fir to the time (k+N)M+N.sub.fir, wherein fir indicates the filter and N.sub.fir represents the filter 120 half-window. The trajectory generator 110 takes the maximal acceleration a.sub.max and the maximal velocity v.sub.max and an ordered list of positions 101 and generates the next portion 602 of the reference trajectory.

(75) FIG. 6C shows how a next filtered reference trajectory for the slow positioning subsystem is generated. This determination is based on an averaging technique carried out by the filter 120, which is centered around the time step k+N where a new position for the slow positioning subsystem is needed. By centering the filtering (averaging) around the time step k+N, the filtered trajectory 112 or slow subsystem reference trajectory 113 for the slow positioning subsystem becomes in phase with the reference trajectory 111 (601). This, however, is not necessary and the filtering (averaging) can be performed on the reference trajectory 111 (601) prior to the time step k+N.

(76) FIG. 6D shows the infeasibility detector 130 assessing the feasibility of the newly added reference trajectory for the slow positioning subsystem. This is performed using the set of linear inequalities, i.e., conditions expressed in equations (12) or (15), for recursive feasibility and condition (16) for persistent tracking derived for this purpose.

(77) FIG. 6E shows how the trajectory slowdown 135 is used to recover from infeasibility by slowing down and regenerating the reference trajectory 111 (602).

(78) Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.