Branch-and-lift algorithm for obstacle avoidance control


  • X. Feng, M.E. Villanueva, B. Chachuat, B. Houska


  • In Proceedings of the
    56th IEEE Conference on Decision and Control,
    Melbourne, Australia, pages 745 - 750, July, 2017.


Obstacle avoidance problems are a class of 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.



author = {X. Feng and M.E. Villanueva and B. Chachuat and B. Houska},
title = {Branch-and-lift algorithm for obstacle avoidance control},
booktitle = {In Proceedings of the 56th IEEE Conference on Decision and Control},
year = {2017},
pages = {745–750},