Comparison of Branching Strategies for Path-Planning with Avoidance using Nonlinear Branch-and-Bound

This paper develops and compares nine geometric branching strategies for use with a nonlinear branch and bound optimisation method, tailored for finding optimal trajectories for a vehicle constrained to avoid fixed obstacles. The key property of the branch and bound optimisation is that it provides globally optimal solutions to the nonconvex pathplanning problems whilst retaining the full nonlinear dynamics model. The solution time depends heavily on the choice of branching strategy, which determines how the solution tree is explored. A good strategy is one that requires fewer tree branches to be enumerated before the global optimal is found and verified. The branching strategies presented can be thought of as two linked decisions: which subproblem to add to the currently active node set; and which node within the currently active node set to next solve. The branch and bound approach used by obstacle branch and bound ensures all branching is geometric in nature and based on the decision of whether to pass an obstacle on the left or on the right, therefore allowing branching strategies to capitalise on direct understanding of the problem. A comparison of the nine branching strategies developed is presented and the best strategy is identified. The best strategy found was 30% faster than the first attempt strategy that had been previously implemented, indicating the importance of strategy choice. In addition, the best of these branching strategies is then compared with an existing Mixed-Integer Linear Programming (MILP) approach and demonstrated a significant improvement on MILP solve times, larger than previously observed.