Branch-and-lift algorithm for obstacle avoidance control
Xuhui Feng, Mario E. Villanueva, Benoît Chachuat, Boris Houska · 2017
Obstacle avoidance problems are a class of non-convex optimal control problems for which derivative-based optimization algorithms often fail to locate global minima. The goal of this paper is to provide a tutorial on how to apply Branch & Lift algorithms, a novel class of global optimal control methods, for solving such obstacle avoidance problems to global optimality. The focus of the technical developments is on how Branch & Lift methods can exploit the particular structure of Dubin models, which can be used to model a variety of practical obstacle avoidance problems. The global convergence properties of Branch & Lift in the context of obstacle avoidance is discussed from a theoretical as well as a practical perspective by applying it to a tutorial example.