UC Santa Cruz

Model predictive control (MPC) is a common approach to the control of trajectory-following systems. For nonlinear plants such as car-like robots, methods for path planning and following have the advantage of concurrently solving problems of obstacle avoidance, feasible trajectory selection, and trajectory following. A prediction function for the plant is used to simulate the trajectory with a candidate stream of inputs. Constraints on control inputs and state values, used to ensure safe trajectories and to avoid obstacles, are encoded into a cost function, and optimization routines (at runtime) compute the trajectories and their corresponding control inputs. Such approaches are computationally intensive, and in the nonlinear case the computational burden generally grows as a predictive model more closely approximates a nonlinear plant. In situations where system safety is paramount, guaranteeing model accuracy (in order to achieve more accurate behavior) comes at the cost of increased computation time, which results in increased travel time without a new solution. While the computational burden of predictive methods can be addressed through model reduction, the cost of modeling error over the prediction horizon is high and can lead to unfeasible results. In this paper, we consider the problem of controlling a ground vehicle under constraints and propose an algorithm that employs two models of the vehicle for model predictive control, one coarse and the other more accurate. We introduce a metric called uncontrollable divergence and, using this metric, propose a mechanism to select the model to use in the predictive controller. The novel property of the metric is that it reveals the divergence between predicted and true states caused by return time and model mismatch. More precisely, a map of uncontrollable divergence plotted over the state space gives the criterion to judge where coarse models can be tolerated when a high update rate is preferred (e.g., at high speed and small steering angles), and where high-fidelity models are required to avoid obstacles or make tighter curves (e.g., at large steering angles). With this metric, we design a controller that switches at runtime between predictive controllers in which respective models are deployed. The algorithm is a hybrid controller, which evaluates the proposed metric to select the discrete vehicle model to use for prediction and optimization. We say that the approach is computationally aware, in that the optimization time of each predictive model is dependent on the computation substrate used (chipset, machine architecture, etc.); if a different computational platform is used, then the uncontrollable divergence calculations will lead to a hybrid controller suitable to meet the computation demands for that platform. While the ideas are presented for the solution of a vehicle control problem, the approach has the potential to impact other computationally-demanding cyber-physical systems. The paper extends (Zhang et al., Proceedings of the international conference on cyber-physical system, Seattle, 2015) in a significant way, by demonstrating the calculation of uncontrollable divergence on a physical platform, by characterizing MPC return time as a function of the number of obstacles, and by simulating performance with trajectories that must navigate more obstacles.