Multi Vehicle Avoidance Using Nonlinear Branch and Bound Optimisation

AJ Eele, AG Richards

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

7 Citations (Scopus)


This paper describes a novel method for finding optimal trajectories for vehicles constrained to avoid one another. 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 (UAVs), air traffic control, and robot path planning. The core concept is the direct application of branch-and-bound optimisation, to find guaranteed, globally-optimal solutions to non-convex problems. This extends the work using nonlinear branch-and-bound optimiation for static obstacle avoidance where significant solve time savings were found against a conventional Mixed-Integer- Linear-Programming (MILP) approach. The proposed method uses the branch-and-bound approach for multi-vehicle avoidance problems by first, using a geometric branching strategy based on the decision for a pair of vehicles to pass one another clockwise or anticlockwise; and second, solving the resulting subproblems by constructing solutions on each chosen "side" and using them to initialise an interior point optimisation. Two alternative methods of constructing initial solutions for initialising the interior point optimisation are proposed and compared. Both methods are then compared to existing Potential Fields and MILP methods demonstrating a significant improvement on MILP solve times for problems with four or more vehicles.
Translated title of the contributionMulti Vehicle Avoidance Using Nonlinear Branch and Bound Optimisation
Original languageEnglish
Title of host publicationAIAA Guidance Navigation and Control Conference, Chicago
Publication statusPublished - Aug 2009

Bibliographical note

Conference Organiser: AIAA
Other identifier: AIAA-2009-5780


Dive into the research topics of 'Multi Vehicle Avoidance Using Nonlinear Branch and Bound Optimisation'. Together they form a unique fingerprint.

Cite this