Recent work (Rantzer, 2022) formulated a class of optimal control problems involving positive linear systems, linear stage costs, and elementwise constraints on control. It was shown that the problem admits linear optimal cost and the associated Bellman's equation can be characterized by a finite-dimensional nonlinear equation, which is solved by linear programming. In this work, we report exact dynamic programming (DP) theories for the same class of problems. Moreover, we extend the results to a related class of problems where the norms of control are bounded while the optimal costs remain linear. In both cases, we provide conditions under which the solutions are unique, investigate properties of the optimal policies, study the convergence of value iteration, policy iteration, and optimistic policy iteration applied to such problems, and analyze the boundedness of the solution to the associated optimization programs. Apart from a form of the Frobenius-Perron theorem, the majority of our results are built upon generic DP theory applicable to problems involving nonnegative stage costs.

Optimal control theory has a long history and broad applications. Motivated by the goal of obtaining insights through unification and taking advantage of the abundant capability to generate data and perform online simulation, this thesis studies the discrete-time infinite horizon optimal control problems and introduces some approximate solution methods via abstract dynamic programming (DP) models. The proposed methods involve approximation in value space through the use of data and simulator, apply to a broad class of problems, and strike a good balance between satisfactory performance and computational expenditure.

First, we consider deterministic problems with nonnegative stage costs. We derive sufficient conditions under which a local controllability condition holds for the constrained nonlinear systems, and apply the results to establish the convergence of the classical algorithms, including value iteration, policy iteration (PI), and optimistic PI. These results provide a starting point for the design of suboptimal schemes. Then we propose algorithms that take advantage of system trajectory or the presence of parallel computing units to approximate the optimal costs. These algorithms can be viewed as variants of model predictive control (MPC) or rollout, and can be applied to deterministic problems with arbitrary state and control spaces, and arbitrary dynamics. It admits extensions to problems with trajectory constraints, and a multiagent structure. Via the viewpoint provided by the abstract DP models, we also derive the performance bounds of MPC applied to unconstrained and constrained linear quadratic problems, as well as their nonlinear counterparts. These insights suggest new designs of MPC, which likely lead to larger feasible regions of the scheme while costing hardly any loss of performance measured by the costs accumulated over infinite stages. 

Moreover, we derive algorithms to address problems with a fixed discount factor on future costs. We apply abstract DP models to analyze $\lambda$-PI with randomization algorithms for problems with infinite policies. We show that a contraction property induced by the discount factor is sufficient for the well-posedness of the algorithm. Moreover, we identify the conditions under which the algorithm is convergent with probability one. Guided by the analysis, we exemplify a data-driven approximate implementation of the algorithm for the approximation of the optimal costs of constrained linear and nonlinear control problems. The obtained optimal cost approximations are applied in a related suboptimal scheme. Then we consider discounted problems with discrete state and control spaces and a multiagent structure. When applying rollout to address the problem, the main challenge is to perform minimization over a large control space. To this end, we propose a rollout variant that involves reshuffling the order of the agents. The approximation of the costs of base policies is through the use of on-line simulation. The proposed approach is applied to address multiagent path planning problems within a warehouse context, where through on-line replanning, the robots can adapt to a changing environment while avoiding collision with each other. 

Optimal reglerteori har en lång historia med mängder av olika tillämpningar. Motiverade av att få insikter genom att förena olika problem och metoder, utnyttja den rika förmågan att generera data samt utföra online-simulering, studerar denna avhandling tidsdiskreta optimala reglerproblem med oändlig tidshorisont och introducerar några ungefärliga lösningsmetoder via abstrakta dynamiska programmeringmodeller (DP-modeller). De föreslagna metoderna innebär att värderummet approximeras då data och simulatorer används, tillämpas på en bred klass av problem samt uppnår en god balans mellan tillfredsställande prestanda och beräkningskostnader.

Vi börjar med att studera deterministiska problem med icke-negativa stegkostnader. Vi härleder tillräckliga villkor som garanterar lokal styrbarhet för icke-linjära regleringssystem med signalbegränsingar och tillämpar resultaten för att fastställa konvergens av de klassiska algoritmerna, inklusive värdeiteration, policyiteration (PI) och optimistisk PI. Dessa resultat ger oss en utgångspunkt för att konstruera suboptimala metoder. Därefter föreslår vi algoritmer som utnyttjar systemtrajektorier eller närvaron av parallella beräkningsenheter för att uppskatta de optimala kostnaderna. Dessa algoritmer kan ses som varianter av modellprediktiv reglering (MPC) eller rollout och kan tillämpas på deterministiska problem med godtyckliga tillstånds- och styrrum, samt godtycklig dynamik. Denna insikt tillåter oss att utvidga våra metoder till problem med begräsningar på trajektoria och multiagentstruktur. Via den abstrakta DP-modellens synpunkt härleder vi även prestandabegränsningar för MPC tillämpat på både icke-begränsade och begränsade linjära kvadratiska problem samt deras icke-linjära motsvarigheter. Dessa insikter föreslår nya konstruktioner av MPC som leder till fler möjliga appliceringsområden för metoden med nästan ingen förlust av prestanda mätt i kostnader som samlas upp över oändliga tidshorisonter.

Dessutom härleder vi algoritmer för att lösa problem med en fix diskonteringsfaktor på framtida kostnader. Vi tillämpar abstrakta DP-modeller för att analysera $\lambda$-PI algoritmer med slumpmässighet för problem med oändliga policyer. Vi visar att en sammandragningsegenskap som orsakas av diskonteringsfaktorn är tillräcklig för att algoritmen ska vara välformulerad. Dessutom identifierar vi villkoren som gör att algoritmen konvergerar med sannolikhet ett. Med ledning av analysen exemplifierar vi en datadriven ungefärlig implementering av algoritmen för att uppskatta de optimala kostnaderna för begränsade linjära och icke-linjära regleringsproblem. De uppskattade optimala kostnaderna används i ett relaterat suboptimal metod. Därefter behandlar vi diskonteringsproblem med diskreta tillstånds- och styrrum och en multiagentstruktur. När vi tillämpar rollout för att hantera problemet är den största utmaningen att utföra minimering över ett stort styrrum. Vi föreslår en rolloutvariant som innebär att ordningen på agenterna ändras för att hantera utmaningen. Uppskattningen av kostnaderna för baspolicyerna sker genom användning av online-simulering. Den föreslagna metoden tillämpas för att hantera ruttplanering för multiagentsystem i ett lager, där robotarna genom online-omplanering kan anpassa sig till en föränderlig miljö samtidigt som de undviker kollision med varandra.

Efficiently solving path planning problems for a large number of robots is critical to the successful operation of modern warehouses. The existing approaches adopt classical shortest path algorithms to plan in environments whose cells are associated with both space and time in order to avoid collision between robots. In this work, we achieve the same goal by means of simulation in a smaller static environment. Built upon the new framework introduced in (Bertsekas, 2021a), we propose multiagent rollout with reshuffling algorithm, and apply it to address the warehouse robots path planning problem. The proposed scheme has a solid theoretical guarantee and exhibits consistent performance in our numerical studies. Moreover, it inherits from the generic rollout methods the ability to adapt to a changing environment by online replanning, which we demonstrate through examples where some robots malfunction.

We study unconstrained and constrained linear quadratic problems and investigate the suboptimality of the model predictive control (MPC) method applied to such problems. Considering MPC as an approximate scheme for solving the related fixed point equations, we derive performance bounds for the closed-loop system under MPC. Our analysis, as well as numerical examples, suggests new ways of choosing the terminal cost and terminal constraints, which are not related to the solution of the Riccati equation of the original problem. The resulting method can have a larger feasible region, and cause hardly any loss of performance in terms of the closed-loop cost over an infinite horizon.

Freight drivers of electric trucks need to design charging strategies for where and how long to recharge the truck in order to complete delivery missions on time. Moreover, the charging strategies should be aligned with drivers' driving and rest time regulations, known as hours-of-service (HoS) regulations. This letter studies the optimal charging problems of electric trucks with delivery deadlines under HoS constraints. We assume that a collection of charging and rest stations is given along a pre-planned route with known detours and that the problem data are deterministic. The goal is to minimize the total cost associated with the charging and rest decisions during the entire trip. This problem is formulated as a mixed integer program with bilinear constraints, resulting in a high computational load when applying exact solution approaches. To obtain real-time solutions, we develop a rollout-based approximate scheme, which scales linearly with the number of stations while offering solid performance guarantees. We perform simulation studies over the Swedish road network based on realistic truck data. The results show that our rollout-based approach provides near-optimal solutions to the problem in various conditions while cutting the computational time drastically.

We consider the sensor scheduling problem for remote state estimation under integrity attacks. We seek to optimize a trade-off between the energy consumption of communications and the state estimation error covariance when the acknowledgment (ACK) information, sent by the remote estimator to the local sensor, is compromised. The sensor scheduling problem is formulated as an infinite horizon discounted optimal control problem with infinite states. We first analyze the underlying Markov decision process (MDP) and show that the optimal scheduling without ACK attack is of the threshold type. Thus, we can simplify the problem by replacing the original state space with a finite state space. For the simplified MDP, when the ACK is under attack, the problem is modeled as a partially observable Markov decision process (POMDP). We analyze the induced MDP that uses a belief vector as its state for the POMDP. We investigate the properties of the exact optimal solution via contractive models and show that the threshold type of solution for the POMDP cannot be readily obtained. A suboptimal solution is then obtained via a rollout approach, which is a prominent class of reinforcement learning (RL) methods based on approximation in value space. We present two variants of rollout and provide performance bounds of those variants. Finally, numerical examples are used to demonstrate the effectiveness of the proposed rollout methods by comparing them with a finite history window approach that is widely used in RL for POMDP.

Optimal control theory has a long history and broad applications. Motivated by the goal of obtaining insights through unification and taking advantage of the abundant capability to generate data, this thesis introduces some suboptimal schemes via abstract dynamic programming models.

As our first contribution, we consider deterministic infinite horizon optimal control problems with nonnegative stage costs. We draw inspiration from the learning model predictive control scheme designed for continuous dynamics and iterative tasks, and propose a rollout algorithm that relies on sampled data generated by some base policy. The proposed algorithm is based on value and policy iteration ideas. It applies to deterministic problems with arbitrary state and control spaces, and arbitrary dynamics. It admits extensions to problems with trajectory constraints, and a multiagent structure.

In addition, abstract dynamic programming models are used to analyze $\lambda$-policy iteration with randomization algorithms. In particular, we consider contractive models with infinite policies. We show that well-posedness of the $\lambda$-operator plays a central role in the algorithm. The operator is known to be well-posed for problems with finite states, but our analysis shows that it is also well-defined for the contractive models with infinite states. Similarly, the algorithm we analyze is known to converge for problems with finite policies, but we identify the conditions required to guarantee convergence with probability one when the policy space is infinite regardless of the number of states. Guided by the analysis, we exemplify a data-driven approximated implementation of the algorithm for estimation of optimal costs of constrained linear and nonlinear control problems. Numerical results indicate the potentials of this method in practice.

Teorin om optimal reglering har en lång historia och breda tillämpningsområden.I denna avhandling, som motiveras av att få insikter genom att förena och dra nyttaav den goda möjligheten att generera data, introduceras några suboptimala systemvia abstrakta modeller för dynamisk programmering.I vårt första bidrag betraktar vi ett deterministiskt optimalt regleringsproblemmed oändlig horisont och icke-negativa stegkostnader. Vi hämtar inspiration frånmodellprediktiv reglering med inlärning, som är utformad för system med kontinuerligdynamik och iterativa uppgifter, och föreslår en utrullningsalgoritm som bygger påsamplade data som genereras av en viss baspolicy. Den föreslagna algoritmen byggerpå idéer om värde- och policyiteration. Den är tillämpningsbar för deterministiskaproblem med godtyckliga tillstånds- och kontrollrum samt för system med godtyckligdynamik. Slutligen kan den utvidgas till problem med trajektoriebegränsningar ochen struktur med flera agenter.Dessutom används abstrakta modeller för dynamisk programmering för attanalysera lambdapolicyiteration med randomiseringsalgoritmer. Vi betraktar merspecifikt kontraktiva modeller med oändliga strategier. Vi visar att lambdaoperatorns välbestämdhet spelar en central roll i algoritmen. Det är känt att operatorn ärväldefinierad för problem med ändliga tillstånd, men vår analys visar att den ocksåär väldefinierad för de studerade kontraktiva modellerna med oändliga tillstånd.På samma sätt är det känt att den algoritm vi analyserar konvergerar för problemmed ändliga strategier, men vi identifierar de villkor som krävs för att garanterakonvergens med sannolikhet ett när policyrummet är oändligt, oberoende av antalettillstånd. Med hjälp av analysen exemplifierar vi en datadriven approximativ implementering av algoritmen för uppskattning av optimala kostnader för begränsadelinjära och icke-linjära regleringsproblem. Numeriska resultat visar på potentialen iatt använda denna metod i praktiken.

We consider deterministic infinite horizon optimal control problems with nonnegative stage costs. We draw inspiration from learning model predictive control scheme designed for continuous dynamics and iterative tasks, and propose a rollout algorithm that relies on sampled data generated by some base policy. The proposed algorithm is based on value and policy iteration ideas, and applies to deterministic problems with arbitrary state and control spaces, and arbitrary dynamics. It admits extensions to problems with trajectory constraints, and a multiagent structure.

dynamic programming models are used to analyze λ-policy iteration with randomization algorithms. Particularly, contractive models with infinite policies are considered and it is shown that well-posedness of the λ-operator plays a central role in the algorithm. The operator is known to be well-posed for problems with finite states, but our analysis shows that it is also well-defined for the contractive models with infinite states studied. Similarly, the algorithm we analyze is known to converge for problems with finite policies, but we identify the conditions required to guarantee convergence with probability one when the policy space is infinite regardless of the number of states. Guided by the analysis, we exemplify a data-driven approximated implementation of the algorithm for estimation of optimal costs of constrained linear and nonlinear control problems. Numerical results indicate potentials of this method in practice.

In this work, we present a novel approach based on linear matrix inequalities to design a linear-time varying model predictive controller for a nonlinear system with guaranteed stability. The proposed method utilizes a multi-model description to model the nonlinear system where the dynamics is represented by a group of linear-time invariant plants, which makes the resulting optimization problem easy to solve in real-time. In addition, we apply the control invariant set designed as the final stage constraint to bound the additive disturbance introduced to the plant by other subsystems interfacing with the controller. We show that the persistent feasibility is ensured with the presence of such constraint on the disturbance of the specified kind. The proposed method is then put into the context of emergency lane change for steering control of automated vehicles and its performance is verified via numerical evaluation.