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

AJ Eele, AG Richards

Research output: Contribution to journalArticle (Academic Journal)peer-review

48 Citations (Scopus)


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 th e 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.
Translated title of the contributionPath Planning with Avoidance using Nonlinear Branch-and-Bound Optimization
Original languageEnglish
Pages (from-to)384 - 394
Number of pages11
JournalJournal of Guidance, Control, and Dynamics
Issue number2
Publication statusPublished - Mar 2009

Bibliographical note

Publisher: AIAA


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

Cite this