Eele, A. & Richards, A.G. Path-Planning with Avoidance using Nonlinear Branch-and-Bound Optimisation, AIAA Guidance, Navigation and Control Conference, 2007
Abstract:
This paper describes a novel method for finding optimal trajectories for a vehicle constrained to avoid fixed obstacles. The key property of the method is that it provides globally optimal solutions to these non-convex problems while retaining the full nonlinear dynamics model. Applications for the new algorithm include the guidance of Uninhabited Aerial Vehicles, air traffic control, and path-planning for robots. The core concept is the direct application of branch-and-bound optimisation, tailored to suit avoidance problems by exploiting two new ideas: first, using a geometric branching strategy based on the decision of whether to pass an obstacle on the left or on the right; and second, solving the resulting subproblems by constructing simple solutions on each chosen "side'' and using them as the initial guesses for primal-dual optimisation techniques. Examples are provided to illustrate the branch-and-bound procedure and show successful determination of optimal paths. A comparison between the initial implementation of the method and an existing Mixed-Integer Linear Programming (MILP) approach is also presented. The results of the solve time comparison indicate in the majority of cases the proposed method was faster than the MILP approach.
