2024 MIDWEST WORKSHOP ON CONTROL AND GAME THEORY

Talk Title

Excursions into Nonstandard LQG Decision Making

Talk Title

Sample Complexity for Discrete System Identification

Abstract

We consider data-driven methods for modeling discrete-valued dynamical systems evolving over networks. The spread of viruses and diseases, the propagation of ideas and misinformation, the fluctuation of stock prices, and correlations of financial risk between banking and economic institutions are all examples of such systems. In many of these systems, data may be widely available, but approaches to identify relevant mathematical models, including the underlying network topology, are not widely established or agreed upon. Classic system identification methods focus on identifying continuous-valued dynamical systems from data, where the main analysis of such approaches largely focuses on asymptotic properties, i.e., consistency. More recent identification approaches have focused on sample complexity, i.e., how much data is needed to achieve an acceptable model approximation. In this talk, we will discuss the problem of identifying a mathematical model from data for a discrete-valued, discrete-time dynamical system evolving over a network. Specifically, under maximum likelihood estimation approaches, we will demonstrate guaranteed sample complexity bounds and consistency conditions. Applications to the aforementioned examples will be further discussed as time allows.

Talk Title

Comparison of Information Structures in Bayesian Social Learning

Abstract

In many settings, agents learn by observing the actions of others. On-line platforms can aid in making such information available, but are also susceptible to manipulation by “fake” agents. Bayesian social learning provides a framework to study such questions. In this framework, agents sequentially make Bayesian optimal decisions given their private information and their observations of prior agent’s decisions. The presence of fake agents degrades the quality of the information available to each agent. In this talk, we review a line of work that studies the impact of changing the information structures on the resulting agent behavior. This is joint work with Pawan Poojary.

Talk Title

Resource Takeover Games for Dynamical Systems

Abstract

Cyber-physical systems have become ubiquitous across various application domains such as home automation, vehicles, smart grids, and medical devices, to name a few. However, their widespread integration also exposes them to the risk of adversarial attacks. An adversarial takeover can lead the system to undesirable states or can even permanently damage the system, resulting in service disruption and potential loss of lives. Although most analysis frameworks designed to recommend security measures cover various classes of attacks and systems, a vast majority of these usually do not address the effects of a complete takeover by one of the players (e.g., the defender resorting to a complete reset after an attack, but at a price). Inspired by the FlipIt model of resource takeovers, we will examine a model in which the resource that both players (a defender and an attacker) are interested in is governed by a dynamical system. The overall system is then represented by a hybrid state, in which the discrete state indicates which player currently controls the system. At each time instance, both players make decisions on whether or not to invest energy in order to gain/retain control of the system, and the choice of the control action. Our main results include analytic expressions for the costs-to-go as a function of the hybrid state. For the case of a continuous system state with linear dynamics and quadratic costs, we will address Nash equilibrium solutions for the game. In particular, for scalar continuous states, we will characterize a closed-form expression of the takeover and control actions. For higher dimensional systems, we will present approximate solutions for the game and the corresponding player policies.

Talk Title

Data-enabled Predictive Control: regularization and robustness

Abstract

Advances in computer science have spurred a large interest in developing data-driven prediction, decision making, and control methods for real-world systems. As these data-driven technologies begin to expand into more complex systems, many new challenges arise regarding safety and reliability, especially since these systems often appear in safety-critical environments with possible human interaction. Thus, one grand challenge in data-driven control is to design data-driven decision-making algorithms that perform reliably in safety-critical and real-time environments and are tractable in terms of computation and sample efficiency. This talk proposes a novel method for data-driven control known as Data-enabled Predictive Control (DeePC) leveraging behavioral systems theory and a result known as the fundamental lemma. The main idea is to replace the parametric dynamical system model with a raw data matrix of time series measurements (trajectories) and use it as a non-parametric predictive model. We study suitable regularization techniques leading to robust performance guarantees in the presence of corrupted data. We illustrate the method using simulations and real-world experiments in robotics and power systems.

Talk Title

Learning for Safety and Control Design in Dynamical Systems

Abstract

AI-based methods have tremendous potential for impacting the performance of autonomous aerospace and robotic systems. Such systems include drones, ground- and water-based vehicles, and limbed robots for instance. A barrier to the wide deployment of AI-powered methods in such applications is the risk or unpredictability of algorithm performance. In this presentation we consider the development of safe machine learning (ML) methods for control that provide guarantees about their convergence and performance. Specifically, the presentation will focus on two distinct topics involving the application of learning techniques to analysis of dynamical systems. First: we present an algorithm and a tool for statistical model checking (SMC) of continuous state space Markov chains initialized to a prescribed set of states. We observe that it can be formulated as an X-armed bandit problem, and therefore, can be solved using hierarchical optimistic optimization. Our experiments, using our tool HooVer, suggest that the approach scales to realistic-sized problems and is often more sample-efficient compared to other existing tools. Second: We will discuss our recent work on exploring the capabilities of state-of-the-art large language models (LLMs), such as GPT-4, Claude 3 Opus, and Gemini 1.0 Ultra, in solving control design problems. In particular, we introduce ControlBench, a benchmark dataset tailored to reflect the breadth, depth, and complexity of classical control design. This study serves as an initial step towards the broader goal of employing artificial general intelligence in control engineering.

Talk Title

Lyapunov-like converse results for strong forward invariance

Abstract

The talk presents sufficient conditions for strong forward invariance of closed or compact sets. The conditions use Lyapunov-like functions, which are positive definite with respect to the invariant sets, are reasonably smooth, and --- usually --- don't increase too fast. The setting is of differential inclusions, where uniqueness of solutions need not be ensured. Connections of these functions to usual Lyapunov functions, for differential inclusions and hybrid dynamics, and to barrier functions that exclude finite-time blow up of solutions, are explored in the proofs. The results come from joint work with A. Teel and R. Sanfelice.

Talk Title

Robust Incentive Design for Non-Myopic Followers

Abstract

In incentive design, a decision-maker, called the leader, aims to induce desired behaviors in one or more agents, called the followers, by influencing their payoffs. Our work studies the setting of a non-myopic follower, who makes sequential decisions and plans by maximizing the cumulative reward, and a leader who can modify the reward of the follower. While algorithms exist for solving the incentive design problem, they rely on several restrictive assumptions about the follower: 1) When the best response is non-unique, the follower breaks ties in favor of the leader; 2) the leader knows perfectly how the modified reward is perceived by the follower; 3) the follower is fully rational. Motivated by the need for removing these assumptions, we study the problem of robust incentive design, where the goal is to obtain a robust strategy for the leader to achieve nearly optimal performance when these assumptions do not hold. We show that such a robust strategy exists under mild conditions and can be numerically computed using mixed-integer linear programming.

Talk Title

Rationality of Learning Algorithms in Repeated Normal-Form Games

Abstract

"Many learning algorithms are known to converge to an equilibrium for specific classes of games if the same learning algorithm is adopted by all agents. However, when the agents are self-interested, a natural question is whether agents have a strong incentive to adopt an alternative learning algorithm that yields them greater individual utility. We capture such incentives as an algorithm's `rationality ratio’, which is the ratio of the highest payoff an agent can obtain by deviating from a learning algorithm to its payoff from following it. We define a learning algorithm to be c-rational if its rationality ratio is at most c irrespective of the game.

We first establish that popular learning algorithms such as fictitious play and regret matching are not c-rational for any constant c greater than or equal to 1. We then propose and analyze two algorithms that are provably 1-rational under mild assumptions and have the same convergence properties as (a generalized version of) fictitious play and regret matching, respectively, if all agents follow them. Finally, we show that if an assumption of perfect monitoring is not satisfied, there are games for which c-rational algorithms do not exist."

Talk Title

Robust Dynamic Staffing with Predictions

Abstract

In this talk, I consider a natural dynamic staffing problem in which a decision-maker sequentially hires staff over a finite time horizon to meet an unknown target demand at the end. The decision-maker also receives a sequence of predictions about the demand that become increasingly more accurate over time. Consequently, the decision-maker prefers to delay hiring decisions to avoid overstaffing. However, workers' availability decreases over time, resulting in a fundamental trade-off between securing staff early (thus risking overstaffing) versus hiring later based on more accurate predictions (but risking understaffing). This problem is primarily motivated by the staffing challenges that arise in last-mile delivery operations. A company such as Amazon has access to flexible gig economy workers (through Amazon Flex) whose availability decreases closer to the target operating day, but they can be hired at any time before that day if they are available.

We study the above problem when predictions take the form of uncertainty intervals that encompass the true demand. The goal of the decision-maker is to minimize the staffing imbalance cost at the end of the horizon against any sequence of prediction intervals being chosen by an adversary. Our main result is the characterization of a simple and computationally efficient online algorithm that obtains the optimal worst-case imbalance cost; said differently, it is minimax optimal. At high level, our algorithm relies on identifying a restricted adversary against which we can characterize the minimax optimal cost by solving a certain offline LP. We then using novel technique show how to "emulate" the LP solution in a general instance (i.e., when facing an unrestricted adversary) to obtain a cost bounded above by the LP's objective. As our base model, we consider staffing for one target demand. We also consider generalizations to multiple target demands with either an egalitarian cost objective (i.e. the worst cost across demands) or a utilitarian cost objective (i.e. sum of costs), and to the case where the hiring decisions can be reversed at given discharging costs. We show how to extend our LP-based emulator minimax optimal policy to these settings.

Talk Title

Modeling, Analysis, and Control of Epidemics Over Networks

Abstract

We present and discuss a variety of mathematical models that have been proposed to capture the dynamic behavior of epidemic processes. We first present traditional group models for which no underlying graph structures are assumed, thus implying that instantaneous mixing between all members of a population occurs. Then we consider models driven by similar principles, but involving non-trivial networks where spreading occurs between connected nodes. We present stability analysis results based on generalizing the idea of the reproduction number to the networked case as well for node-level reproduction numbers. Given the demonstrated validity of the model, we discuss how these models can be leveraged to develop control strategies for mitigating spread. We present a safety-critical optimal control approach for group models. Finally, we conclude by discussing an ongoing project that leverages collaboration in networked epidemics to ensure safety-critical control of an outbreak in the form of a distributed control algorithm that ensures safety guarantees among cooperating agents.

Talk Title

Sharing Experience

Abstract

Consider a group of individuals whose decisions can be guided by others’ experiences. In an efficient outcome, individuals take turns making choices and share their experiences with everyone else. Equilibrium information sharing, on the other hand, resembles a war of attrition, since individuals trade off the losses from waiting to consume with the gains associated with learning from their predecessors. The likelihood of equilibrium sequential choices depends not only on the behavior of past decision-makers, but also on the composition of those waiting to decide.

Talk Title

Reconstruction of interconnectedness in networks of dynamical systems based on passive and partial observations: connections to Causation

Abstract

Determining interrelatedness structure of various entities from multiple time series data is of significant interest to many areas. Knowledge of such a structure can aid in identifying cause and effect relationships, clustering of similar entities, identification of representative elements and model reduction. In this talk, a methodology for identifying the interrelatedness structure of dynamically related time series data based on passive observations will be presented. The framework will allow for the presence of loops in the connectivity structure of the network. The quality of the reconstruction will be quantified. In the second part of the talk, with more structure assumed on the dynamics and structure, techniques for unveiling cause-effect relations will be presented. Results on the extent of the recovery of the network structure where only a subset of entities are observed and under corruption of data will be highlighted. The talk will also present an application to analog circuits.

Talk Title

Systematic analysis of iterative black-box optimization algorithms using control theory

Abstract

Iterative algorithms are used to solve optimization problems throughout control, robotics, statistics and estimation, signal processing, communication, networks, machine learning, and data science. Recent work from both optimization and control communities has developed a systematic methodology to analyze the worst-case performance of a black-box algorithm over a class of problems. In this talk, we first describe this systematic methodology from a controls perspective and then show how it can be used to analyze and design algorithms in various contexts, such as trading off convergence rate and robustness to gradient noise with noisy first-order oracles, consensus optimization for a multi-agent system, and primal-dual algorithms.

Talk Title

Optimal Control in Animal Sensorimotor Systems

Abstract

In this talk, I will describe the role of optimal control in both behavioral and implementation models of animal sensorimotor control. In some sense, animals behave like an optimal controller — but how is this optimal controller implemented in the brain and body of the animal, and what are the additional theory developments needed to adequately model this? Neurons do not communicate the same way that transistors do — this translates to communication delays and constraints that play a significant role in shaping the physiological implementation of biological controllers.

Talk Title

Leveraging Transfer Learning for Centralized Fleet Management in Intrafactory Logistics

Abstract

As production facilities increasingly prioritize resilience in their logistical operations, the replacement of assembly lines with fleets of autonomous mobile robots (AMRs) has emerged as a key factor in achieving autonomous intrafactory logistics. To ensure uninterrupted production despite unpredictable disruptions, fleet management systems must reroute AMRs and reallocate material handling tasks to minimize incurred costs and downtime. Given the challenge of making these combinatorial decisions in real time, decentralized approaches are appealing due to their real-time performance. However, the resulting solutions are sub-optimal and do not leverage the resilience offered by the entire fleet. Our research addresses the challenge of enabling centralized fleet management (CFM) through the combination of classic optimization methods with data-driven approaches. In this talk, we discuss a transfer-learning approach that exploits a core feature of intrafactory logistics: every product’s manufacturing process prescribes a nominally defined material handling requirement. When a disruption causes a change in this nominal requirement, the CFM leverages insights from the previous explorations of the nominal decision space to produce feasible solutions in real-time with lower optimality gaps than decentralized approaches. The last part of the talk will discuss how this novel CFM method enables the deployment of adversarial learning techniques to delineate safe and critical perturbations.

Talk Title

Rethinking Online Content Ecosystems in the Era of Generative AIs

Abstract

The open Internet is all about contents, which used to be created, consumed, shared and evaluated all by humans. In the past few decades, many successful platforms like TikTok and Google have formed various online content ecosystems that on one hand properly match user interests to the right contents and one the other hand incentivize content creators to generate fresh and high-quality contents. However, recent significant advances in generative AIs (GenAIs) is revolutionizing the way contents are created, which could be much less costly, possibly even more creative though possibly with lower quality and depending on the available amount of human-created contents to sustainably refine GenAI's model training. This is fundamentally changing the underlying logic and incentives of existing content ecosystem. If not addressed properly, this may lead to distorted incentives for human creators and potentially disastrous outcomes of driving humans out of the system. In this talk, I will present our recent works that integrate machine learning, multi-agent system modeling and incentive design to (a) understand the economics and evolution dynamics of these online content ecosystems and (b) study how GenAI-based content creation could potentially re-shape these ecosystems. I will conclude with many open questions. We believe a thorough understanding of these questions is critical to ensure our Internet ecosystem will steer towards the era of GenAI safely and sustainably.

Talk Title

Proactive Robot Control for Collaborative Manipulation Using Human Intent

Abstract

For robots to be functional in a human environment, it is essential that their behavior feels comfortable to humans. That is, robots must perceive clues from various modalities, generate legible actions, take initiative, and follow human initiative when necessary. This talk explores controller design for a human-robot collaborative manipulation task. In particular, we focus on the case where the two participants need to negotiate where to move the object when the goal destination is not uniquely specified, and who should lead the motion. Our work is motivated by the ability of humans to communicate the desired destination of motion through back-and-forth force exchanges. Inherent to these exchanges is also the ability to dynamically assign a role to each participant, either taking the initiative or deferring to the partner's lead. We propose a hierarchical robot control framework that emulates human behavior in communicating a motion destination to a human collaborator and in responding to their actions. The control architecture is loosely based on the strategy observed in the human-human experiments, and the key component is a real-time intent recognizer that helps the robot respond to human actions. The talk will conclude with a description of the results of a human study that was used to validate the proposed controller.

Talk Title

Safety-Critical Control Under Uncertainties

Abstract

This talk is focused on efficient control of safety-critical real-world systems subject to model uncertainties. In the first part of the talk, I will discuss uncertainty compensation (UC) based approaches, showcasing how UC can be applied to develop effective predictive control schemes capable of handling a broad class of uncertainties. Additionally, I will introduce efficient learning-based control schemes that ensure safety during the learning transients. In the second part of the talk, I will delve into robust approaches, with a focus on the leveraging of contraction theory in designing and learning nonlinear tracking controllers that minimize the effect of uncertainties while providing performance and robustness guarantees.