11.2.1 Description of Predictive Control Principles in Generalized Form

The methodology implied in predictive control not only opens a broad development space for solving various optimization control problems, as mentioned above, but also provides a good inspiration for solving more general optimization and decision problems in a dynamic uncertain environment. In various application fields, there exist a large number of dynamic processes where optimization or decision is required, such as robot path planning, production planning and resource scheduling, discrete event dynamic system (DEDS) monitoring and so on. For quite a long time this kind of problem is often attributed to off‐line solving an optimization problem, but it should not be ignored where the optimization result needs to be implemented in an actual dynamic environment where uncertainty inevitably exists. Therefore, different from optimization in a pure mathematical sense, we call this kind of optimization‐based problem with implementation in the dynamic environment a general control problem.

Compared with traditional control problems, these general control problems have different structural characteristics and cannot be directly solved by existing control theory based on the dynamic mathematical model. Therefore, at first the focus is always on exploring effective optimization algorithms according to the structural characteristics of the problem. These studies often take a complete and accurate description of the problem under discussion as the premise and try to find the global optimal solution of the problem by developing an appropriate optimization strategy in terms of the prior information. Obviously, once the obtained optimal solution is put into practice, it would remain optimal if both the model and the environment are exactly as assumed. However, if the actual status deviates from the assumed one, such as the environmental map is inaccurate or an obstacle moves, the production conditions or demands change, the resource supply fails, the discrete event process varies with time, etc. then the optimum status could not be maintained, even if a serious deterioration of system performance resulted. Therefore this optimal solution off‐line solved by prior information cannot guarantee an actual optimum in the dynamic uncertain environments. This is just the same problem encountered when applying the traditional optimal control to practical industrial processes.

In the real environment, the incomplete and inaccurate information, the uncertainty of the plant, the dynamic variation of the environment, and so on, are inevitable. For the general control problems, the offline global optimization takes into account the requirements of optimization, but no consideration is given to the dynamic uncertainty of the environment. In fact, in most cases complete information on the plant and the environment is difficult to obtain and accurately predict. The global optimization based on that is thus impossible or meaningless due to the unknown variation of the plant and the environment. In addition, global optimization often involves large‐scale computation, which must also be considered from the viewpoint of implementation. Therefore, for various optimization‐based general control problems, in order to obtain a practically available solution, the solving method should combine the optimization mechanism with a feedback mechanism, and remove the unnecessary global optimization style. It is obvious that the general control problems in a dynamic uncertain environment face a similar problem to that in complex industrial process control. Since predictive control can meet the requirements on control in a complex industrial environment with its specific methodological principles, its methodological thinking can be naturally applied to solving the general control problems in a dynamic uncertain environment. Therefore, it is necessary to generalize the basic principles of predictive control from being originally only applicable to control problems to a more inclusive methodological framework. The generalized principles of predictive control are shown in Figure 11.1 and can be described as follows [2].

1. Scenario prediction

   Although the structures of various general control problems are different, as a kind of problem to be solved with optimization, it is necessary to establish a prediction model to describe the dynamic scenario of the problem. This model should contain all the known information about the problem to be solved, especially the causality for the evolution of the scenario, the evolution law, the constraint conditions, and the objective of optimization. The input of the scenario prediction model is the required strategy and the output is the dynamic evolution of the system states. According to this model, if the current status is known and the future decision strategy is given, the dynamic evolution of the process scenario can be predicted, with which the satisfaction of the constraints can be judged and the corresponding performance index can be calculated. Therefore, the scenario prediction model is a generalization of the prediction model in predictive control, with the strategy to be solved as the input and the performance to be optimized as the output.

2. Rolling window optimization

   To solve the general control problem, the traditional method using off‐line global optimization is replaced by a rolling window method using online local optimization repeatedly. At each step of the rolling procedure, a rolling window is first determined based on current status according to certain rules. Only the local optimization problem in the rolling window will be solved by using scenario prediction and optimization techniques. The optimal strategy in the rolling window can be obtained but only the current strategy is put into implementation. With the evolution of the dynamic process, the window is moved forward according to some driving mechanism; thus we call it rolling window optimization. The rolling window here can be defined in time domain, space domain, event domain, etc. according to the problem structure. Thus the driving mechanism of the rolling window can be defined as being periodic driven, event driven, etc. according to the characteristics of the problem.

3. Feedback initialization

   At each step of the rolling procedure, before starting the local optimization, the status in the new rolling window should be firstly reinitialized (updated) according to real‐time information. This means that the scenario description in the rolling window is not just a mapping of the evolution predicted by the global or the latest scenario model, but also includes the deviation information of the scenario prediction model as well as the scenario variations caused by uncertain and unpredictable events. The feedback initialization ensures that the local optimization at each step is based on the latest real‐time information.

These three generalized principles promote the predictive control from only solving control problems to solving general control problems in a dynamic uncertain environment. Among these principles the scenario prediction is the generalization of the prediction model, which describes more general dynamic causality of general control problems instead of the input–output relation in a narrow sense. It exhibits the dynamic evolution process of the problem to be solved in a wider sense, and thus provides the basis for solving the optimal strategy according to the optimization performance index. Making local optimization in the rolling window is partly because it is impossible and also unnecessary to take into account the performance index in a global scope. Furthermore, reducing the scale of the optimization problem makes it convenient to solve in real time. Rolling window optimization combined with feedback initialization can make the optimization always based on real‐time information such that the uncertainty and the dynamic variations of the environment can be included and considered timely in the optimization. Thus the overall problem solving is an ongoing process and runs in the closed‐loop form. These principles embody the combination of the optimization mechanism and the feedback mechanism. It provides an ideal combination for solving the optimization‐based general control problems in the dynamic uncertain environment.

In the following subsections, the above‐mentioned generalized principles of predictive control are illustrated in more detail by some typical examples.

11.2.2 Rolling Job Shop Scheduling in Flexible Manufacturing Systems

Scheduling problems widely exist in many application fields where some specific requirements on cost, efficiency, etc., should be optimized with respect to constraints on general resources. Typical scheduling problems include production planning, job scheduling, pickup and delivery, etc. In particular, the job scheduling problem is widely investigated and used in modern manufacturing systems due to the requirement for production optimization.

In flexible manufacturing systems (FMSs), the job shop scheduling problem can be described as follows. A batch of jobs should be processed. Each of them has to go through a series of ordered operations to complete the processing. There are several machines. Each machine can process a set of operations, which may be different for different machines. The jobs belong to some job classes and different classes of jobs have different operations. The processing time of the same operation on different machines may also be different. Furthermore, each job is assigned a due date according to the class it belongs to. The scheduling problem is: when and on which machine to arrange each operation of each job such that the total makespan for all jobs, i.e. the minimum time to complete the operations of all jobs, is minimized, while the due date constraints for the jobs are satisfied. It is obviously a combinational optimization problem.

In the past, many researches on FMS job shop scheduling were focused on static scheduling, i.e. finding efficient scheduling algorithms with the assumption that all jobs are available and ready for processing. Once the schedule is prepared, the processing sequence of jobs is determined and not changed during processing. In the actual process, however, the obtained optimal schedule cannot guarantee the desired results because the assumption for static scheduling is often too idealistic. Indeed, the production is always in a dynamic uncertain environment where jobs arrive continuously and unpredictable events, such as machine breakdown, machine repair and due date changes of jobs, may occur. In this case, a dynamic scheduling strategy is needed and predictive control can provide an excellent methodology to construct a suitable dynamic scheduling strategy. Inspired by the generalized principles of predictive control, Fang and Xi [3] proposed a rolling horizon job shop scheduling strategy to the above problem in the dynamic uncertain environment, with specific implementations as follows.

(1) Scenario prediction

The prediction model of the job shop production can be established based on appropriate description of following two kinds of information:

• Prior information, including the operations required for each class of jobs and their order, the executable operations and corresponding processing time of each machine, due date of each class of job.
• Real‐time information, including job status, machine status, due date change of jobs, etc.

This model is indeed an information set with the schedule to be solved as input and the production status as output. With this information set the job processing procedure can be simulated and the dynamic scenario of the manufacturing process can be exhibited. Once a schedule is given, the variation of production status could be calculated, with which it can be judged whether the schedule is reasonable, whether the due date constraints for the jobs are satisfied, and the corresponding total make‐span can be calculated.

(2) Rolling window optimization

In the case when many jobs need to be processed but uncertain events or accident may occur, it is unnecessary to make a schedule for all the jobs. A job window is then constructed by selecting a number of jobs from jobs waiting for processing according to some specific rules. Only jobs in the job window are scheduled and partially processed according to the scheduling results. In the following some key points will be discussed in more detail.

1. Job window. According to the actual production environment, it is assumed that jobs arrive continuously and the future arrival time of some unavailable jobs is known. Therefore, the job set can be divided into three subsets: the available job set Sa, jobs in the current job window Sw_, and jobs that have completed their operations Sc. For the selection rule, we first give a quantitative urgency index to each job in the available job set Sa with which a job with an earlier arrival time or with an estimated finish time much later than its due date may have a higher degree of urgency. Choose the job with the highest urgency in the available job set Sa and move it into the job window Sw until the number of jobs in Sw reaches the given number or Sa is empty. Only the jobs in the job window Sw are scheduled with the help of the scenario prediction, and the resultant schedule is used to arrange the current operations. This procedure will be repeated until all jobs have finished their operations.
2. Scheduling problem formulation. At each step, a scheduling problem is defined on the current job window Sw. The goal of optimization is to minimize the local production makespan, i.e. the completion time for processing all the jobs in the job window. Usually an additional term to penalize the tardy time of jobs is also needed in the performance index, which takes the due date constraints of jobs into consideration. The constraints in the optimization problem include a series of equalities or inequalities due to technological conditions, such as the relationship between the makespan and the operation time of jobs on the machines, the condition that for each job the finish time of its any operation is not later than the start time of its following operation, etc. all of which are related to the information given by the prediction model. The optimal solution, i.e. the optimal schedule for the jobs in the job window, is given by the release time of each operation with a corresponding machine for all jobs.
3. Scheduling problem solving. For the above scheduling problem it is obvious that there are two key problems to be solved, i.e. to dispatch every operation of jobs to suitable machines and to determine the processing sequence and release time of jobs on each machine. With respect to the former problem, the size of search space is in general large because many jobs and multiple machines are often involved for job shop scheduling. For the latter problem, the constraints are often difficult to handle, such as the job operation sequence must be satisfied and at any time each job appears at most on one machine, etc. To avoid the difficulty from both a large search space and complicated constraints, [3] proposed a hybrid scheduling algorithm. Since the genetic algorithm (GA) is suitable for searching a large solution space, it is adopted to decide on which machine each operation should be processed. As the dispatching rule is simple where the operation sequence constraints are easily satisfied, it is used to arrange the processing sequence of jobs on each machine, and accordingly to determine the release time of jobs. The details on designing the algorithm can be found in [3]. It should be pointed out that this scheduling algorithm is a heuristic one and different dispatching rules may yield different optimal solutions.
4. Rolling mechanism. In general, the job window is rolling forward periodically with a fixed time or with completion of a fixed number of jobs. However, as mentioned above, the resultant actual performance may be poor due to the dynamic uncertain environment. To overcome the drawback, [3] proposed a periodic and event‐driven mechanism. Some typical unpredictable events, such as machine breakdown, machine repair, and due date change of jobs, are defined as critical events. If a critical event occurs, rescheduling is performed immediately; otherwise periodic rescheduling is adopted. This rolling strategy combined with feedback initialization discussed below forms a specific and efficient mechanism against the dynamic uncertainties for the job shop scheduling problem.

(3) Feedback initialization

During rescheduling and before solving the optimal schedule, both the scenario prediction model and the real‐time job status should be initialized according to the latest feedback information on the production process and possible critical events. New jobs will be moved into the available job set Sa when their arrival time becomes known. The jobs in Sw should be updated, i.e. jobs that have finished their operations are moved into Sc and new jobs are selected from Sa to Sw according to the selection rule. Furthermore, the scenario prediction model should be updated according to possible changes of the job due date and the machine status such that the scheduling for the jobs in the updated job window can be based on the latest processing capability and satisfy the updated requirements.

Fang and Xi [3] also gave an example of 30 jobs processed on four machines to illustrate the rolling job shop scheduling strategy. The 30 jobs belong to three classes J1, J2, and J3 with the job index 1–10 in J1, 11–20 in J2, and 21–30 in J3. The operations needed for each class of jobs with their sequences are given by: J1: A‐C‐B‐D, J2: B‐D‐E, J3: B‐A‐F, and the operations that each machine can process are: m1: (A, B, C, F), m2: (B, C, D, E), m3: (B, D, F), m4: (E, F). The process times of operations on four machines and the set‐up times from one operation to another on the four machines are known (not listed here). The due dates of three classes of jobs are: 300, 400, and 500, respectively. The jobs arrive dynamically over time and the arrival times of jobs are set randomly from the range of (0, 300). At any time only the arrival times of the incoming jobs that will arrive within a prediction period T_P can be exactly known and these jobs can then be added to the available job set. Some unpredictable events during processing are considered: at time t = 100 machine m2 breaks down and will be repaired at time t = 200, and at time t = 150 the due dates of J3 jobs will be changed from 500 to 350. In order to evaluate the dynamic scheduling results, the performance measure of the production makespan plus a weighted (taken as 0.65) penalty term on tardy time of jobs is taken as the criterion.

In the rolling window scheduling strategy, the maximum number of jobs in the job window is set as L_W = 10, the interval of the periodic rescheduling ΔT = 40, and the predictive period T_P = 60. The scheduling result obtained is shown by grant charts in Figure 11.2.

In Figure 11.2, the square stands for the processing time of the related operations including the set‐up time and the processing time of the operation, the character inside the square stands for the operation being processed, and the integer above the square is the job index the operation belongs to, where R stands for the rescheduling point. The related makespan L = 579.23 and the performance measure C = 1813.03. As a comparison, the static scheduling result using the same method solved once for the global scheduling problem is given in Figure 11.3, the related makespan L = 643.77, and the performance measure C = 3040.86.

The simulation results show that the rolling window scheduling strategy is more suitable for the dynamic uncertain environment than the static scheduling strategy. Firstly, after the due date change of J3 jobs from 500 to 350, with static scheduling, the J3 jobs are still processed later than J2 jobs although their due date is now earlier than that of J2 jobs. However, with rolling window scheduling, J3 jobs are processed earlier and J2 jobs are postponed to be processed later. Secondly, with static scheduling, jobs are processed according to the processing sequence decided by the schedule. After machine m2 breaks down, due to the postponement of scheduled job operations processing on m2, and the constraints on job operation sequences, the three other machines have a period of idle time and the production efficiency is considerably degraded. With rolling window scheduling, however, when machine m2 breaks down, rescheduling is performed immediately and the jobs waiting to be processed by machine m2 are dispatched to other machines, such as the operation D of job 9 being processed in machine m2 is moved to machine m3 to continue processing. After machine m2 is repaired, rescheduling is also performed at once and jobs are again dispatched to it for processing. Therefore the makespan derived by the rolling window scheduling strategy is shorter than that by the static one, and so is the whole cost.

The rolling window scheduling strategy has obvious advantages for FMS in a dynamic uncertain environment. The job window and its rolling mechanism is particularly suitable to real‐time implementation because the scale of each scheduling is greatly reduced although the scheduling needs to be repeated online. The feedback initialization has a quick response to unpredictable events, so that the scheduling at each time is always based on the real production status. In addition, this rolling mechanism is fully applicable to the cases where jobs have an unlimited number to arrive continuously, which cannot be handled by traditional scheduling methods. More details on the above algorithm and example can be found in [3]. A similar strategy also appeared in some later literature. In Wang et al. [4] a terminal penalty rolling scheduling strategy based on an initial schedule is proposed and investigated for a single‐machine scheduling problem. Referring to the stable predictive controller design, a penalty function is added to the total completion time of the scheduling problem in the job window and this technique guarantees an improvement of the global performance over time.

11.2.3 Robot Rolling Path Planning in an Unknown Environment

The path planning problem of a mobile robot aims at finding a proper collision‐free moving path for the mobile robot from a designated start point to a designated goal point in its workspace by using available environmental information. There are two extreme cases. One case is that the environmental information is fully known. In this case the feasible path or even the optimal path with respect to some performance index (such as the shortest path) can be solved by global planning methods. It has been extensively investigated and much literature with different solving methods have been published. Another case is that no prior knowledge of the global environment is available and the robot can only use the real‐time environmental information detected by the sensors to move toward the goal by circumventing obstacles. In this case, optimizing the path is meaningless and the robot even possibly falls into a dead zone and fails to reach the goal. The above two extreme cases correspond, respectively, to the open‐loop global planning based on complete environmental information and the closed‐loop immediate navigation based on locally feedback information. However, the practical environmental information is often somewhere in between. On the one hand, there is always enough prior knowledge of the environment. For example, when an autonomous vehicle transports materials in a production workshop, the information on fixed obstacles such as machines, materials, stores, etc. can be obtained beforehand. On the other hand, the environmental information is often incomplete or inaccurate. For example, the obstacles from walking people or vehicles in the workshop are unpredictable and the piles might increase or decrease during the production.

Path planning of a mobile robot with incomplete information in an uncertain environment cannot be solved by traditional global planning methods. The navigation methods based on immediate feedback information are unable to provide a satisfactory solution due to lack of optimization, and even hardly guarantee the accessibility. However, note that the robot could detect some environmental information in a finite region under its sensor scope during motion, so this part of the information should be fully used. Therefore, a reasonable way to solve this problem is to fully use detected local environmental information and to adopt local planning repeatedly instead of the off‐line global planning. Zhang and Xi [5] proposed a rolling window based method for robot path planning in globally unknown environments. It is along the lines of the generalized principles of predictive control mentioned in Section 11.2.1. In the following we introduce specific implementations of this method.

(1) Scenario prediction

To exhibit the scenario of the robot moving in the environment, a prediction model is established based on the information of the robot’s motion and the environment, as well as the planning task. It includes some prior knowledge such as the robot kinematics, known static obstacles in the map of the environment, and the start point and the goal point of the planning task, as well as some real‐time information, such as the detected current positions of the mobile robot itself and moving obstacles.

According to this model, the robot motion scenario in the environment can be demonstrated. For any given moving path from the start point to the goal point, whether the robot is collided with static or moving obstacles can be judged and, if not, the corresponding performance index can be calculated.

(2) Rolling window optimization

Since global environmental information is not available, a rolling window based path planning strategy is performed instead of the off‐line global path planning. At each step of the rolling process, the rolling window is defined as a specific region around the robot and with the robot as its center, which should be included in the detectable region of the robot sensor system. Path planning is then performed within this rolling window based on the latest local information.

Information on the rolling window

The environmental information on the rolling window consists of two parts, coming from prediction model and feedback initialization, respectively. On the one hand, prior knowledge of the global environment included in the prediction model, such as robot kinematics, positions of known static obstacles (if any), should be mapped into the current window. On the other hand, the real‐time detected new information in the rolling window, such as static obstacles that might be unknown before or moving obstacles with trajectory predictions, should be also included.

Subgoal determination and local path planning

For local path planning in the rolling window, the current position of the robot is naturally taken as the start point. However, the known goal point designated by the task may be out of the current window and cannot be directly taken as the goal point of the local path planning. Aiming at this specific problem, [5] proposed a heuristic method based on local detected information, which first determines a subgoal located at the border of the current window and then plans an optimal path from the current position of the robot to the subgoal in the rolling window.

Denote the rolling window and its border at time t as Win(P_R(t)) and ∂Win(P_R(t))_, respectively, where P_R(t) is the position of the robot, i.e. the center of the current window. Let P_goal be the known goal point designated by the task and P_sub(t) be the subgoal to be determined. If the robot is very close to the goal point, i.e. P_goal ⊂ Win(P_R(t)), then P_goal can be directly taken as the goal point of local path planning. Otherwise, a heuristic function f(P) = g(P) + h(P) is used to determine a point P on the border of the rolling window as the subgoal P_sub(t) that minimizes f(P), namely

where g(P) denotes the cost (path length) from current position P_R(t) to P and h(P) denotes the cost from P to the known goal point P_goal. Since the environmental information out of the window is unknown, h(P) is usually estimated by the distance from P to the goal P_goal. Solving the above optimization problem we can obtain both the subgoal P_sub(t) and the optimal local path in the window, with which and the straight path out of the window f(P) is minimized. This method reflects the compromise of the requirement on global optimization and the restriction of finite local information.

The above optimization problem can be solved using different strategies. To reduce the computational burden, in [5] the problems of determining the subgoal and planning the local path were separately solved. At first g(P) is simply set as zero or infinite according to P in feasible region or not, then the subgoal P_sub(t) can be easily taken as the point P at the feasible border of the rolling window which has the minimal distance to the goal point P_goal. After the subgoal has been determined, a strictly nearer feasible path planning algorithm is presented for local path planning, which guarantees that along the path the distance to the goal decreases with time.

Obstacle avoidance

Obstacle avoidance is the most critical issue in robot path planning. During local path planning, the environment map with static obstacles has been updated and the planned path can easily guarantee that the robot is collision free with these static obstacles. However, for any dynamic obstacle, although it may have been detected, collision might occur in a general sense due to the uncertainty of its future motion. To handle a dynamic obstacle, some conditions on its shape, motion, etc., should be given, such as with convex shape, constraints on changes of its direction or speed, and so on. Then the future path of the dynamic obstacle can be estimated and possible collision can be avoided by using a proper planning strategy. For details readers can refer to, for example, [6].

(3) Feedback initialization

Path planning based on the rolling window is performed periodically. After the local path has been determined, the robot will move one step forward along the planned path until the next period. At each new period, the robot first acquires real‐time environmental information through its sensor system, and initializes the environment map with the latest information on obstacles in the window. It not only corrects the prior known information on static obstacles in the window but also identifies the unknown dynamic obstacles, and even predicts the future motion path of these dynamic obstacles. All this information is used to update the prediction model in the current window, with which the local path planning can be performed based on the latest and most practical information.

In Figure 11.4 a simulation example of rolling path planning for a mobile robot in a globally unknown dynamic environment is shown. The moving circle is the rolling window with the mobile robot at its center and the environmental information within it is fully detectable by the robot sensor system. S is the start point and G is the known goal point. The large gray convex bulks represent unknown static obstacles, while the small circles with trailing tails represent the unknown dynamic obstacles with irregular motions. The actual tracks of these four dynamic obstacles are marked by a series of short lines.

At the beginning of rolling path planning, the robot does not possess any prior information on static and dynamic obstacles. At each step, the robot firstly detects environmental information in the current window and updates the positions of the obstacles. Then an appropriate path in the rolling window is planned that guarantees collision avoidance and satisfies some optimization criterion. The robot moves along this local path one step forward and this process is repeated until the goal is reached. In Figure 11.4 this procedure for some specific instants are shown, where the black parts represent the obstacle information gradually detected by the robot during the procedure. It can be seen that with the rolling path planning method the robot can safely reach the goal point according to the repeatedly planned path.

The rolling path planning method for a mobile robot adopts repeated local optimization performed online instead of global optimization. It is particularly suitable to the path planning problem in a globally unknown environment, even with dynamic obstacles. Meanwhile, the path planning based on the local window reduces the scale of the optimization problem to be solved and is thus easy to implement in real time. Some theoretical aspects such as convergence of the algorithm, suboptimality of the resultant path, etc., were also discussed for the case with globally unknown static obstacles [5, 7]. The path planning strategy for dynamic obstacles in the local window and the safety analysis of the resultant path can be found in [6].

In addition to the above discussed robot path planning and FMS job shop scheduling problems in a dynamic environment, many other general control problems, such as network real‐time optimization and management, DEDS real‐time monitoring, transportation scheduling, investment decision, etc. can also be solved by similar principles. Although their implementation forms and solving algorithms may be quite different due to problem specifications and uncertainty differences, the idea is the same, i.e. to make full use of all causal information for prediction and optimization, and meanwhile to update the information continuously by rolling combined with feedback, so that the optimization and decision at each step can be based on the latest information. The generalization of the predictive control principles to the general control problems in the dynamic uncertain environment will also open up wider fields and provide richer modes for applications of predictive control.