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

AJ Eele, AG Richards

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

4 Citations (Scopus)


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.
Translated title of the contributionComparison of Branching Strategies for Path-Planning with Avoidance using Nonlinear Branch-and-Bound
Original languageEnglish
Title of host publicationAIAA Guidance, Navigation and Control Conference, Honolulu, USA
PublisherAmerican Institute of Aeronautics and Astronautics Inc. (AIAA)
Publication statusPublished - Aug 2008

Bibliographical note

Conference Organiser: AIAA
Other identifier: AIAA 2008-6463


Dive into the research topics of 'Comparison of Branching Strategies for Path-Planning with Avoidance using Nonlinear Branch-and-Bound'. Together they form a unique fingerprint.

Cite this