Utilizing Reachability Analysis in Point Location Problems

Recent results in parametric mathematical programming established that the explicit piecewise affine solution to some optimal control problems can be defined on a partition of the state space. An optimal feedback control law is associated with each member of the state space partition. Instead of solving an optimization problem online at every time instant, the recent, so-called explicit, MPC schemes require merely the identification of the member of the solution partition that contains the measured state. Once this set is found, the affine optimal control law associated with the set is evaluated and applied to the system. This set-membership problem is referred to as the point location problem. We demonstrate that, under mild assumptions, the point location problem only needs to be solved at the initialization of the control scheme rather than at every time instant. Given a member of the solution (state-space) partition, the system dynamics and the explicit control law are utilized to obtain the set of states that can be reached at the next time instant. The members of the partition intersecting this one-step forward reach set are, under our assumptions, guaranteed to contain the process state at next point in time. A direct consequence of the presented results is the fact that it is sufficient to solve a reduced point location problem instead of resolving the entire point location problem at every time instant