Path-Planning with Avoidance Using Nonlinear Branch-and-Bound Optimization

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 while retaining the full nonlinear dynamics model. Applications for the method include guidance of unmanned aerial vehicles, air traffic control,and robot path planning. The core concept is the direct application of branch-and-bound optimization to find guaranteed, globally optimal solutions to nonconvex problems. The method tailors the branch-and-bound approach specifically for avoidance problems by exploiting two new ideas: first, using a geometric branching strategy based on the decision between passing an obstacle clockwise or counterclockwise; and second, solving the resulting subproblems by constructing simple solutions on each chosen "side" and using them to initialize an interior-point optimization. The algorithm is refined by comparing nine geometric branching strategies. The solution time of the method depends on the choice of branching strategy, which determines how the solution tree is explored. A good strategy is one requiring fewer tree branches to be enumerated before the global optimal is found. The best of these branching strategies has been compared with an existing mixed-integer linear programming approach and demonstrated a significant improvement on mixed-integer linear programming solve times.