A graph search algorithm for optimal control of hybrid systems

For optimally controlling hybrid automata with nonlinear continuous dynamics and discrete as well as continuous inputs, an approach combining graph search techniques with principles of optimal control has recently been proposed. The main idea is to embed nonlinear programming and hybrid system simulation into a graph search algorithm that selects the discrete degrees of freedom. When applying this approach, it can be observed that often large numbers of almost identical evolutions of the hybrid system are explored with no (or marginal) improvement of the system performance. In order to obtain a better coverage of the hybrid search space, the method is here extended by the notion of adjacency criteria. The principle is to determine locally optimal trajectories from the set of almost identical evolutions, to postpone the evaluation of suboptimal ones, and thus to obtain qualitatively different solutions with low effort. The adjacency criteria can either be used as a search heuristics or, if a near-optimal solution is sufficient, to prune the search graph.