Approximate Methods of Optimal Control via Dynamic Programming Models

• 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.

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Reglerteknik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Control Engineering (hsv//eng)

Nyckelord

Optimal Control; Dynamic Programming; Rollout; Model Predictive Control

Electrical Engineering

Elektro- och systemteknik

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)