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 contribution||Multi Vehicle Avoidance Using Nonlinear Branch and Bound Optimisation|
|Title of host publication||AIAA Guidance Navigation and Control Conference, Chicago|
|Publication status||Published - Aug 2009|
Bibliographical noteConference Organiser: AIAA
Other identifier: AIAA-2009-5780