The project focuses on the use of the max-plus algebra as a tool for the solution of nonlinear control and estimation problems. The main classes of problems addressed are those for which the associated dynamic programming equation takes the form of a nonlinear Hamilton-Jacobi-Bellman partial differential equation (HJB PDE). The semigroups associated with such problems are time-indexed operators which are max-plus linear. The max-plus linearity may be exploited to develop numerical methods for HJB PDEs, which might be described as (max-plus) spectral methods. These form a completely new class of numerical methods for HJB PDEs. The project will also consider approaches where one can construct complex operators in the semiconvex dual space from operators for simpler problems such as linear-quadratic problems. This allows one to avoid the curse-of-dimensionality in the most computationally intensive portion of the computations in max-plus based methods for problems whose operators may be approximated by such constructions in the dual-space.
Control Theory is useful for any system where one desires to estimate the true state of the system and/or to control its future behavior. The methods of control theory apply to a tremendous variety of real-world systems such as aircraft dynamics, spacecraft dynamics, portfolio optimization, option pricing, and collections of robotic vehicles. Although the control of systems whose behavior is close to linear has been quite successful, there are many problems where the system behavior may be highly nonlinear, and the number of such problems is on the rise. The solution of nonlinear control problems is quite difficult, and not computationally tractable for systems whose states are described by more than just two or three scalar variables. The solution of such problems is most often obtained by the solution of an associated partial differential equation. The most common approach has been to adopt finite element methods (often used to solve problems such as fluid flow) in order to solve such partial differential equations, and consequently, the control problems. However, the computational requirements grow exponentially fast as a function of the number of scalar state variables.
This is commonly referred to as the curse-of-dimensionality. Due to this exponential growth in computational cost, we cannot hope that faster computers will lead to solution of reasonably large problems in the foreseeable future. Therefore, we must explore alternative approaches to the solution of such problems. In this project, we apply a new class of methods to such nonlinear control problems. These methods exploit the fact that these nonlinear problems are linear over a different set of algebraic operations known as the max-plus algebra. By employing this max-plus linearity, one can obtain new numerical methods that appear to provide computational savings. Although one cannot hope to completely remove the curse-of-dimensionality, these methods should attenuate its effects.
