Search

Model predictive controllers use dynamics models to solve constrained optimal control problems. However, computational requirements for real-time control have limited their use to systems with low-dimensional models. Nevertheless, high-dimensional models arise in many settings, for example, discretization methods for generating finite-dimensional approximations to partial differential equations can result in models with thousands to millions of dimensions. In such cases, reduced-order models (ROMs) can significantly reduce computational requirements, but model approximation error must be considered to guarantee controller performance. In this article, a reduced-order model predictive control (ROMPC) scheme is proposed to solve robust, output feedback, constrained optimal control problems for high-dimensional linear systems. Computational efficiency is obtained by using projection-based ROMs, and guarantees on robust constraint satisfaction and stability are provided. The performance of the approach is demonstrated in simulation for several examples, including an aircraft control problem leveraging an inviscid computational fluid dynamics model with dimension 998 930. [ABSTRACT FROM AUTHOR]

Pickup and delivery problems (PDPs), in which objects or people have to be transported between specific locations, are among the most common combinatorial problems in real-world logistical operations. A widely-encountered type of PDP is the Stacker Crane Problem (SCP), where each commodity/customer is associated with a pickup location and a delivery location, and the objective is to find a minimum-length tour visiting all locations with the constraint that each pickup location and its associated delivery location are visited in immediate, consecutive order. The SCP is NP-Hard and the best known approximation algorithm only provides a 9/5 approximation ratio. In this paper, we examine an embedding of the SCP within a stochastic framework, and our objective is three-fold: First, we describe a large class of algorithms for the SCP, where every member is asymptotically optimal, i.e., it produces, almost surely, a solution approaching the optimal one as the number of pickups/deliveries goes to infinity; moreover, one can achieve computational complexity O(n^2+\varepsilon) within the class, where n is the number of pickup/delivery pairs and \varepsilon is an arbitrarily small positive constant. Second, we characterize the length of the optimal SCP tour asymptotically. Finally, we study a dynamic version of the SCP, whereby pickup and delivery requests arrive according to a Poisson process, and which serves as a model for large-scale demand-responsive transport (DRT) systems. For such a dynamic counterpart of the SCP, we derive a necessary and sufficient condition for the existence of stable vehicle routing policies, which depends only on the workspace geometry, the distributions of pickup and delivery points, the arrival rate of requests, and the number of vehicles. Our results leverage a novel connection between the Euclidean Bipartite Matching Problem and the theory of random permutations, and, for the dynamic setting, exhibit novel features that are absent in traditional spatially-distributed queueing systems. [ABSTRACT FROM AUTHOR]