Direct multiple shooting method for solving approximate shortest path problems

摘要

We use the idea of the direct multiple shooting method (presented by Bock in Proceedings of the 9th IFAC World Congress Budapest, Pergamon Press, 1984, for solving optimal control problems) to introduce an algorithm for solving some approximate shortest path problems in motion planning. The algorithm is based on a direct multiple shooting discretization that includes a collinear condition (a continuity condition type in the direct multiple shooting method), multiple shooting structure, and approximation conditions. In the case of monotone polygons, it is implemented by a C code, and a numerical example shows that our algorithm significantly reduces the running time and memory usage of the system.