CIMMS Lunchtime Series: Distributed Optimization for Multiple Aircraft and Airlines

Claire Tomlin, Associate Professor, Dept of Aero/Astro, Stanford University, and Dept of EECS, UC Berkeley

We present a simple decentralized algorithm to solve optimization problems  involving cooperative agents.  Cooperative agents share a common objective and  simultaneously pursue private goals. Furthermore, agents are constrained by limited communication capabilities.  The algorithm is based on dual decomposition  techniques and appears to be very intuitive. It solves the dual problem of an artificially decomposed version of the primal problem, replacing one large computationally intractable problem with many smaller tractable problems. It returns a feasible solution to the primal problem as well as an upper bound on the distance between this solution and the global optimum.  Both convex and nonconvex examples of multiple interacting aircraft are presented.  In the second part of the talk, the methodology is extended to treat multiple, competing airlines in the National Airspace System.

Joint work with Robin Raffard, Steven Waslander, and Stephen Boyd.