Conference Paper: Path-Planning with Avoidance using Nonlinear Branch-and-Bound Optimisation

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.

Conference Paper: Efficient Path Optimization with Terrain Avoidance

G. Keith, J. Tait and A. G. Richards, "Efficient Path Optimization with Terrain Avoidance," AIAA Guidance, Navigation and Control Conference, August 2007.

Abstract: This paper presents a new algorithm for optimal path planning subject to terrain avoidance constraints. The new method extends an existing approach based on Mixed-Integer Linear Programming (MILP) to offer significant improvements in computational efficiency, while guaranteeing globally optimal solution of the path-planning problem. This improvement is the result of three key enhancements. First, the terrain representation is reformulated as a piecewise affine function, resulting in a better conditioned MILP problem. Second, an efficient method of approximating and simplifying real terrain data is developed. Finally, an iterative MILP solution approach is adopted, reducing computational effort by avoiding the application of redundant constraints. The new method is shown to offer significant reductions in solution time for only small loss of performance in terms of the planning objective.