Guest lecture by Yuchao Li, KTH

Abstract:
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, we study the discrete-time optimal control problems and introduce some approximate solution methods via abstract dynamic programming (DP) models.

First, we consider deterministic problems with nonnegative stage costs. Via the viewpoint provided by the abstract DP models, we derive the performance bounds of model predictive control (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. As an application of related schemes, we study optimal charging problems of electric trucks with delivery deadlines under hours of service constraints. 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.

Moreover, we derive algorithms to address problems with a fixed discount factor on future costs. In particular, 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.

Welcome!

Yuchao Li and Nikolce Murgovski