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.
