Intelligent Decision-Making using Bilevel Programming for Autonomous Systems

Abstract

Bilevel optimization problems are hierarchical decision-making problems in which an optimization problem is nested inside another. They provide a powerful modeling framework in domains such as multi-agent autonomous control and constrained trajectory optimization. Large, nonconvex bilevel problems that arise from realistic applications are especially challenging to solve using existing solution paradigms, which fall into two families: reformulation-based and metaheuristic. This dissertation focuses on reformulation-based paradigms, because metaheuristic methods lack a solid theoretical foundation, provide no optimality guarantees, and are generally not suitable for applications with strict performance and safety constraints. There are two main reformulation-based approaches: Local (MPEC-based) and global (MIP-based). Global methods make use of branching MIP algorithms, which makes them applicable to a broad class of bilevel problems, but do not scale well to larger problems because of the combinatorial growth in the search tree. On the other hand, available local methods are usually restricted to linear/convex lower-level problems, making them unsuitable for nonconvex bilevel problems that motivate this work. This dissertation bridges this gap by constructing a fast, local solver methodology and algorithm that can deal with continuous, smooth, nonconvex, standard optimistic bilevel problems which arise from realistic problems. The first part of this dissertation develops the theoretical foundations of bilevel optimization, surveys existing solution paradigms and solvers, and introduces a scalable local method and algorithm using the single-level KKT-reformulation of the bilevel problem, which resolves the complementarity conditions through the identification of locally feasible subregions of the lower-level solution set. The proposed algorithm employs standard solvers on a collection of nonlinear subproblems with regular inequality constraints, and it is validated and benchmarked on a large bilevel test problem library. The second part of the dissertation focuses on three applications and extensions enabled by the proposed approach: Competitive two-player racing, polyhedral collision avoidance, and risk-aware optimization for constrained Markov Decision Processes.