Infinite-horizon optimal control of constrained piecewise affine (PWA) systems has been approximately addressed by hybrid model predictive control (MPC), which, however, has computational limitations, both in offline design and online implementation. In this article, we consider an alternative approach based on approximate dynamic programming (ADP), an important class of methods in reinforcement learning. We accommodate nonconvex union-of-polyhedra state constraints and linear input constraints into ADP by designing PWA penalty functions. PWA function approximation is used, which allows for a mixed-integer encoding to implement ADP. The main advantage of the proposed ADP method is its online computational efficiency. Particularly, we propose two control policies, which lead to solving a smaller-scale mixed-integer linear program than conventional hybrid MPC, or a single convex quadratic program, depending on whether the policy is implicitly determined online or explicitly computed offline. We characterize the stability and safety properties of the closed-loop systems, as well as the suboptimality of the proposed policies, by quantifying the approximation errors of value functions and policies. We also develop an offline mixed-integer-linear-programming-based method to certify the reliability of the proposed method. Simulation results on an inverted pendulum with elastic walls and on an adaptive cruise control problem validate the control performance in terms of constraint satisfaction and CPU time.

This paper proposes an approach to find the eigenvalues and eigenvectors of a class of autonomous max-min-plus-scaling (MMPS) systems. First we show that time invariant, monotone and non-expansive MMPS systems with only time variables has a unique structural eigenvalue and eigenvector under some conditions. Then, we propose a mixed integer linear programming (MILP) algorithm to calculate the eigenvalue and the corresponding eigenvector for such systems. Finally, we present a modified linear programming (LP) algorithm to find all the eigenvalues of a general time invariant MMPS system.

Approximate dynamic programming (ADP) faces challenges in dealing with constraints in control problems. Model predictive control (MPC) is, in comparison, well-known for its accommodation of constraints and stability guarantees, although its computation is sometimes prohibitive. This paper introduces an approach combining the two methodologies to overcome their individual limitations. The predictive control law for constrained linear quadratic regulation (CLQR) problems has been proven to be piecewise affine (PWA) while the value function is piecewise quadratic. We exploit these formal results from MPC to design an ADP method for CLQR problems with a known model. A novel convex and piecewise quadratic neural network with a local–global architecture is proposed to provide an accurate approximation of the value function, which is used as the cost-to-go function in the online dynamic programming problem. An efficient decomposition algorithm is developed to generate the control policy and speed up the online computation. Rigorous stability analysis of the closed-loop system is conducted for the proposed control scheme under the condition that a good approximation of the value function is achieved. Comparative simulations are carried out to demonstrate the potential of the proposed method in terms of online computation and optimality.

We consider the growth rate of a switching max-min-plus-scaling (S-MMPS) system in a discrete-event framework. We show that an explicit, time-invariant, monotone, and arbitrarily switching MMPS system has a bounded growth rate. Further, we propose a mixed-integer linear programming problem to calculate the estimates of the smallest upper bound and the largest lower bound of the growth rate of an S-MMPS system.

In this paper, we discuss the stability of general time-invariant discrete-event systems modelled as max-min-plus-scaling (MMPS) systems. We analyze MMPS systems with two types of states: time states and quantity states. A set of linear programming problems are proposed to find the growth rates of the time states via a normalization of the MMPS system. Then a framework for stability analysis of the general time-invariant MMPS system is discussed with respect to the normalized system. The approach presented in this paper is an efficient way to study the stability of a general MMPS system.

In this paper we discuss modelling and control of discrete-event systems using max-min-plus-scaling systems. We analyse how the basic operations max, min, plus, and scaling occur in the modelling phase and we discuss some general forms for the system. Because of the different/deviating character of the signals in a discrete-event MMPS model, we will discuss concepts such as time-invariance and steady-state behavior. In the design of a model predictive controller for MMPS systems we have to revisit the cost functions in light of the discrete-event nature of the signals. We finalize this paper with the an intuitive case study on an urban railway line, performing both modelling and control.

This paper considers the inland waterborne transport (IWT) problem, and presents a scheduling approach for inland vessels and locks to generate optimal vessel and lock timetables. The scheduling strategy is designed in the switching max-plus-linear (SMPL) systems framework, as these are characterized by a number of features that make them well suited to represent the IWT problem. In particular, the resulting model is linear in the max-plus algebra, and SMPL systems can switch between modes, an interesting feature due to the presence of vessel routing and ordering constraints in the model. Moreover, SMPL systems can be transformed into mixed-integer linear programming (MILP) problems, for which efficient solvers are available. Finally, a realistic case study is used to test the approach and assess its effectiveness.

Railways are a well-recognized sustainable transportation mode that helps to satisfy the continuously growing mobility demand. However, the management of railway traffic in large-scale networks is a challenging task, especially when both a major disruption and various disturbances occur simultaneously. We propose an automatic rescheduling algorithm for real-time control of railway traffic that aims at minimizing the delays induced by the disruption and disturbances, as well as the resulting cancellations of train runs and turn-backs (or short-turns) and shuntings of trains in stations. The real-time control is based on the Model Predictive Control (MPC) scheme where the rescheduling problem is solved by mixed integer linear programming using macroscopic and mesoscopic models. The proposed resolution algorithm combines a distributed optimization method and bi-level heuristics to provide feasible control actions for the whole network in short computation time, without neglecting physical limitations nor operations at disrupted stations. A realistic simulation test is performed on the complete Dutch railway network. The results highlight the effectiveness of the method in properly minimizing the delays and rapidly providing feasible feedback control actions for the whole network.

The class of max-plus-linear systems can model discrete event systems with synchronization but no choice. Model mismatch and/or disturbances can be characterized as stochastic uncertainties. In stochastic max-plus-linear systems one often needs to compute the expectation of a max-plus-scaling (MPS) function or the chance constraint of a MPS function. The algorithms available in literature are either computationally too expensive or only give an approximation. In this article, we derive an analytic expression for both the expectation and the chance constraint of a MPS function. Both can be written in the form of a piecewise polynomial function in the components of the control variables. The analytic function can be derived offline and can be evaluated online in a quick and efficient way. We also show how the expressions can be used in a model predictive control setting and show the efficiency of the proposed approach with a worked example.

This paper considers global optimization of a continuous nonconvex piecewise affine (PWA) function over a polytope. This type of optimization problem often arises in the context of control of continuous PWA systems. In literature, it has been shown that the given problem can be formulated as a mixed integer linear programming (MILP) problem, the worst-case complexity of which grows exponentially with the number of polyhedral subregions in the domain of the PWA function. In this paper, we propose a solution approach that is more efficient for continuous PWA functions with a large number of polyhedral subregions. The proposed approach is based on optimistic optimization, which uses hierarchical partitioning of the feasible set and which can guarantee bounds on the suboptimality of the returned solution with respect to the global optimum given a prespecified finite number of iterations. Since the function domain is a polytope with arbitrary shape, we introduce a partitioning approach by employing Delaunay triangulation and edgewise subdivision. Moreover, we derive the analytic expressions for the core parameters required by optimistic optimization for continuous PWA functions. The numerical example shows that the resulting algorithm is faster than MILP solvers for PWA functions with a large number of polyhedral subregions.

The railway sector is currently experiencing a rapid evolution from fully manual towards automatic rail traffic control systems, due to the growth of transport demand and networks complexity. One of the main issues is to automatically and effectively reschedule the railway traffic in case of unexpected events, thus avoiding dramatic drops in the system performance. In the literature, the majority of contributions aims at automatically minimizing the train delays or optimizing the railway system performance (e.g., energy consumption). However, such strategies are not always able to ensure satisfaction of passengers that in many cases experience the side-effects of the rescheduling actions (e.g., cancellation of train runs, cancellation of coincidences, rerouting of trains, etc.). In this paper, we propose a demandoriented train rescheduling automatic technique that minimizes simultaneously the train delays and the discomfort perceived by passengers. When an unexpected event occurs, the rescheduling problem is set, based on the current state and nominal timetable of the system and its passengers flows. Hence, the problem is solved providing the control actions necessary to minimize both the delays and number of passengers subject to severe side-effects. The rescheduling is here formulated as a mixed integer linear programming problem, where the operating rules of the railway network are represented by linear equality and inequality constraints, while the objective is a linear function to be minimized. The possible control actions consist in re-timing the rail traffic and modifying the connections among lines. The proposed technique is preliminarily evaluated on a test case and a discussion is provided on the outcomes.

In this paper we discuss scheduling of semi-cyclic discrete-event systems, for which the set of operations may vary over a limited set of possible sequences of operations. We introduce a unified modeling framework in which different types of semi-cyclic discrete-event systems can be described by switching max-plus linear (SMPL) models. We use a dynamic graph to visualize the evolution of an SMPL system over a certain period in a graphical way and to describe the order relations of the system events. We show that the dynamic graph can be used to analyse the structural properties of the system. In general the model predictive scheduling design problem for SMPL systems can be recast as a mixed integer linear programming (MILP) problem. In order to reduce the number of optimization parameters we introduce a novel reparametrization of the MILP problem. This may lead to a decrease in computational complexity.

The objective of this paper is to provide a concise introduction to the max-plus algebra and to max-plus linear discrete-event systems. We present the basic concepts of the max-plus algebra and explain how it can be used to model a specific class of discrete-event systems with synchronization but no concurrency. Such systems are called max-plus linear discrete-event systems because they can be described by a model that is “linear” in the max-plus algebra. We discuss some key properties of the max-plus algebra and indicate how these properties can be used to analyze the behavior of max-plus linear discrete-event systems. Next, some control approaches for max-plus linear discrete-event systems, including residuation-based control and model predictive control, are presented briefly. Finally, we discuss some extensions of the max-plus algebra and of max-plus linear systems.

The topic of this paper is model predictive control (MPC) for max-plus linear systems with stochastic uncertainties the distribution of which is supposed to be known. We consider linear constraints on the inputs and the outputs. Due to the uncertainties, these linear constraints are formulated as probabilistic or chance constraints, i.e., the constraints are required to be satisfied with a predefined probability level. The proposed chance constraints can be equivalently rewritten into a max-affine (i.e., the maximum of affine terms) form if the linear constraints are monotonically nondecreasing as a function of the outputs. Based on the resulting max-affine form, two methods are developed for solving the chance-constrained MPC problem for stochastic max-plus linear systems. Method 1 uses Boole's inequality to convert the multivariate chance constraint into univariate chance constraints for which the probability can be computed more efficiently. Method 2 employs Chebyshev's inequality and transforms the chance constraint into linear constraints on the inputs. The simulation results for a production system example show that the two proposed methods are faster than the Monte Carlo simulation method and yield lower closed-loop costs than the nominal MPC method.

The real-time rescheduling of railway traffic in case of unexpected events is a challenging task. This is mainly due to the complexity of the railway service, which has to ensure safety, punctuality, and efficiency to customers by respecting timetable, framework, and resources constraints. Most of the available researches focus on short delays (i.e., disturbances). Approaches typically rely on simplified macroscopic models for large-scale systems or detailed microscopic models for one or a few lines, due to the long computation time required for solving the rescheduling problem. Only a small number of works consider rescheduling in case of long delays (i.e., disruptions) and all of them are also based on either a macroscopic or a microscopic model. This research focuses on disruptions and aims at filling the gap between macroscopic and microscopic modelling by proposing an innovative bi-level rescheduling algorithm based on a mesoscopic Mixed Integer Linear Programming (MILP) model. The technique allows obtaining a feasible rescheduled timetable in a short computation time respecting not only timetable and safety constraints (typical of macroscopic models) but also capacity and ordering constraints for the disrupted stations (typical of microscopic models). The bi-level algorithm first solves the macroscopic MILP rescheduling problem and then, considering the cancellation and non-admissible platform assignments results, it solves a mesoscopic MILP rescheduling problem. This allows to significantly reduce the search space and consequently the computation time. The method is tested for the rescheduling of the Dutch railway traffic in case of a full blockade between two consecutive stations.

We introduce a distributed optimization method for improving the computational efficiency of real-time traffic management approaches for large-scale railway networks. We first decompose the whole network into a pre-defined number of regions by using an integer linear optimization approach. For each resulting region, a mixed-integer linear programming approach is used to address the traffic management problem, with micro details of the network and incorporated with the train control problem. For handling the interactions among regions, an alternating direction method of multipliers (ADMM) algorithm based solution approach is developed to solve the subproblem of each region through coordination with the other regions in an iterative manner. A priority rule based solution approach is proposed to generate feasible suboptimal solutions, in case of lack of convergence. Numerical experiments are conducted based on the Dutch railway network to show the performance of the proposed solution approaches, in terms of effectiveness and efficiency. We also show the trade-off between solution quality and computational efficiency.