Graph Search for Optimizing the Discrete Location Sequence in Hybrid Optimal Control

If an optimal control problem (OCP) for hybrid systems with autonomous switching is solved by use of the hybrid minimum principle (HMP), it is necessary to apply the HMP to each possible discrete location sequence separately, i.e. the complexity is exponential in the number of switches. To reduce the combinatorial complexity, this paper proposes a graph search algorithm where the graph encodes the location sequence and the underlying OCP is solved by using the HMP. First, the hybrid OCP with autonomous switching is relaxed to a problem with controlled switching. When tightening the relaxation iteratively, a branch-and-bound scheme is used to prune the graph for reducing the search space for the optimal location sequence. The efficiency of the algorithm is illustrated for a numerical example.