TBA
Hierarchical structure naturally arises in a wide variety of multi-agent scenarios, from supply chain management to vehicle platooning. Unfortunately though, even bilevel problems are notoriously difficult to solve. This talk will review recent progress in two more general, and in some sense complementary, cases. First, we will show that when follower agents have isolated local best responses to leaders’ decisions, we can find local solutions to tree- and forest-structured problems, with complexity scaling polynomially in the problem depth. Second, we will investigate a classical setting which violates this assumption of isolated best responses: lexicographic optimization, where agents optimize for high priority objectives before lower-priority objectives. In this setting, we derive a compact representation of the first-order equilibrium conditions that circumvents the exponential growth in the number of primal and dual variables (with respect to problem depth) that makes existing transcriptions intractable.
Learning enabled services are revolutionizing several engineering domains such as robotics, mobility, energy, and online marketplaces. While significant progress has been made in developing autonomous agents that operate in isolation, deploying them in dynamic, multi-agent environments presents new theoretical, algorithmic, and societal challenges. Towards this goal, this talk will introduce a novel theoretical framework—Markov near-potential functions (MNPFs)—to study multi-agentinteractions in dynamic environments. It will be shown how this framework can be leveraged to design competitive, real-time planning and control strategies for autonomous multi-car racing. Additionally, we will present a new multi-agent reinforcement learning pipeline – Near-Potential Policy Optimization – which exploits the structure of MNPFs to compute low-regret approximate Nash strategies in general-sum dynamic games.
To truly transform our lives, autonomous systems must operate in complex environments shared with other agents. For instance, delivery robots need to move through spaces that are shared with humans, and warehouse robots must coordinate in shared factory floors. Such multi-agent settings demand systematic methods that enable efficient and reliable interactions among agents. This talk will focus on control challenges in such domains and will discuss game-theoretic planning and control for robots. Intelligent interaction requires robots to reason about how their decisions affect and are affected by others. We will present recent results showing how exploiting structural properties of interactions leads to motion planning algorithms that are both efficient and tractable for real-time deployment on robots in interactive tasks.
From autonomous vehicles navigating busy intersections to mobile manipulators deployed in household environments, robots must operate safely and efficiently around people in uncertain and unstructured situations. Yet today’s robots still struggle to robustly handle human-induced uncertainty without sacrificing efficiency when working closely with people. This talk will argue that reasoning in the joint space of physical states and belief variables capturing human uncertainty offers a unifying lens for safe and performant human–robot interaction (HRI). We introduce a belief-augmented safety filtering framework that combines robust safety analysis with probabilistic inference to enable assured interactions across diverse HRI scenarios. We will then show how such filters can be scalably synthesized via game-theoretic reinforcement learning, yielding robust yet smooth robot behaviors. Finally, we present a belief-augmented dynamic game in which a robot coach helps a human learner acquire and retain motor skills.
Electric endurance racing is characterized by severe energy constraints and strong aerodynamic interactions. Determining race-winning policies therefore becomes a fundamentally multi-agent, game-theoretic problem. These policies must jointly govern low-level driver inputs as well as high-level strategic decisions, including energy management and charging. This talk presents a bi-level framework for competitor-aware race management that combines game-theoretic optimal control with reinforcement learning. At the lower level, a multi-agent game-theoretic optimal control problem is solved to capture aerodynamic effects and asymmetric collision-avoidance constraints inspired by motorsport rules. Using this single-lap problem as the environment, reinforcement learning agents are trained to allocate battery energy and schedule pit stops over an entire race. The framework is demonstrated in a two-agent, 45-lap simulated race. The results show that effective exploitation of aerodynamic interactions is decisive for race outcome, with strategies that prioritize finishing position differing fundamentally from single-agent, minimum-time approaches.
Game-theoretic models and solution concepts provide rigorous tools for predicting collective behavior in multi- agent systems. In practice, however, different agents may rely on different assumptions to synthesize their strategies. As a result, when these heterogeneous models interact, the realized outcome can deviate substantially from the outcome each agent expects based on its own local model. In this talk, we will discuss the game-to-real gap, a new metric that quantifies the impact of such model misspecification in multi-agent environments. The game-to-real gap is defined as the difference between the utility an agent actually obtains in the multi-agent environment (where other agents may have misspecified models) and the utility it expects under its own game model. We will discuss recent work in quantifying the magnitude of the game-to-real gap. Additionally, we will discuss the dynamics of agent interactions with these misspecifications in the context of game-theoretic model predictive control. We will share new stability criteria, equilibria sensitivity, and numerical analyses on the change in the system’s equilibrium as misspecification and the planning horizon vary.
Generalized Nash equilibria are used in multi-agent control applications to model strategic interactions between agents that are coupled in the cost, dynamics, and constraints, and provide the foundations for game-theoretic MPC (Receding Horizon Games). We study properties of finite-horizon dynamic GNE trajectories from a system-theoretic perspective. We show how strict dissipativity generates the turnpike phenomenon in GNE solutions. Moreover, we establish a converse turnpike result, i.e., the implication from turnpike to strict dissipativity. We derive conditions under which the steady-state GNE is the optimal operating point and, using a game value function, we give a local characterization of the geometry of storage functions. Finally, we design linear terminal penalties that ensure dynamic GNE trajectories applied in open-loop converge to and remain at the steady-state GNE. These connections provide the foundation for future system-theoretic analysis of GNEs similar to those existing in optimal control as well as for recursive feasibility and closed-loop stability results of game-theoretic MPC.
We present an efficient algorithm to compute the explicit open-loop solution to both finite and infinite-horizon dynamic games subject to state and input constraints. Our approach relies on a multiparametric affine variational inequality characterization of the open-loop Nash equilibria and extends the classical explicit constrained LQR and MPC frameworks to multi-agent non-cooperative settings. A key practical implication is that linear-quadratic game-theoretic MPC becomes viable even at very high sampling rates for multi-agent systems of moderate size. We will then show a stability and infinite-horizon performance guarantee result based on the design of the agents’ terminal objectives.