SIAM Journal on Control and Optimization, Vol.39, No.3, 835-851, 2000
Optimal control of a class of linear hybrid systems with saturation
We consider a class of rst order linear hybrid systems with saturation. A system that belongs to this class can operate in several modes or phases; in each phase each state variable of the system exhibits a linear growth until a specified upper or lower saturation level is reached, and after that the state variable stays at that saturation level until the end of the phase. A typical example of such a system is a traffic signal controlled intersection. We develop methods to determine optimal switching time sequences for rst order linear hybrid systems with saturation that minimize criteria such as average queue length, worst case queue length, average waiting time, and so on. First we show how the extended linear complementarity problem (ELCP), which is a mathematical programming problem, can be used to describe the set of system trajectories of a rst order linear hybrid system with saturation. Optimization over the solution set of the ELCP then yields an optimal switching time sequence. Although this method yields globally optimal switching time sequences, it is not feasible in practice due to its computational complexity. Therefore, we also present some methods to compute suboptimal switching time sequences. Furthermore, we show that if there is no upper saturation, then for some objective functions the globally optimal switching time sequence can be computed very efficiently. We also discuss some approximations that lead to suboptimal switching time sequences that can be computed very efficiently. Finally, we use these results to design optimal switching time sequences for traffic signal controlled intersections.