Simultaneous orthogonal collocation decomposition method for extended Lion and Man problems

Lion and Man problems are classical examples of pursuit and evasion games. However, the traditional analytic methods and indirect numerical methods only can handle the generalization of Lion and Man problems in games with small scales and simple scenarios. In this study, we first extend the original Lion and Man problems to a more complicated and time-varying game environment. Then we propose the simultaneous orthogonal collocation decomposition (SOCD) method, which is a direct method for exploring solutions of Lion and Man problems in a complicated game environment. Compared to indirect methods, SOCD method is much easier to apply. The max-minimization problem in Lion and Man problems is decomposed into two subproblems of optimal control, which are discretized by using the orthogonal collocation method. Local solutions of the resulting nonlinear programming problems lead to the optimal control problems. We also develop the receding horizon optimization method based on SOCD method to solve Lion and Man problems online in a time-varying game environment. In this method, the whole optimization time domain is divided into several short optimization cycles, and Lion and Man problems in each cycle are based on real-time observations of the game environment. The validity of these two methods is tested by conducting numerical simulations, and the results demonstrate that these methods provide a unified framework for solving extended Lion and Man problems.