Xiaoming Duan

Chendi Qu, Jianping He, Xiaoming Duan

This paper addresses the Direct Data-Driven Inverse Optimal Control (3DIOC) problem for linear time-invariant (LTI) systems under the linear quadratic (LQ) control. Unlike traditional approaches that require system identification, the proposed method learns the underlying objective function directly from measured input-output trajectories. Leveraging the input-output representation of LTI systems via the Fundamental Lemma, we derive a model-free optimality necessary condition (ONC) for the forward LQ problem, which forms the basis for formulating and solving an inverse optimal control problem. We also provide an identifiability condition to ensure the uniqueness of the inverse solution. While the ONC-based IOC approach is effective in the noise-free case, its performance is not promising when the data is corrupted with noises. We then reformulate the 3DIOC as a bi-level optimization problem, which is solved using iterative gradient descent and offers solution guarantees. Furthermore, we analyze the relationship between the solution sets of the two proposed formulations, providing practical insights into their selection. The simulation results validate the effectiveness and performance of our proposed methods.

Xiaoming Duan, Francesco Bullo

This article surveys recent advancements of strategy designs for persistent robotic surveillance tasks with the focus on stochastic approaches. The problem describes how mobile robots stochastically patrol a graph in an efficient way where the efficiency is defined with respect to relevant underlying performance metrics. We first start by reviewing the basics of Markov chains, which is the primary motion model for stochastic robotic surveillance. Then two main criteria regarding the speed and unpredictability of surveillance strategies are discussed. The central objects that appear throughout the treatment is the hitting times of Markov chains, their distributions and expectations. We formulate various optimization problems based on the concerned metrics in different scenarios and establish their respective properties.

Rui Yan, Xiaoming Duan, Zongying Shi et al.

This paper introduces two metrics (cycle-based and memory-based metrics), grounded on a dynamical game-theoretic solution concept called sink equilibrium, for the evaluation, ranking, and computation of policies in multi-agent learning. We adopt strict best response dynamics (SBRD) to model selfish behaviors at a meta-level for multi-agent reinforcement learning. Our approach can deal with dynamical cyclical behaviors (unlike approaches based on Nash equilibria and Elo ratings), and is more compatible with single-agent reinforcement learning than alpha-rank which relies on weakly better responses. We first consider settings where the difference between largest and second largest underlying metric has a known lower bound. With this knowledge we propose a class of perturbed SBRD with the following property: only policies with maximum metric are observed with nonzero probability for a broad class of stochastic games with finite memory. We then consider settings where the lower bound for the difference is unknown. For this setting, we propose a class of perturbed SBRD such that the metrics of the policies observed with nonzero probability differ from the optimal by any given tolerance. The proposed perturbed SBRD addresses the opponent-induced non-stationarity by fixing the strategies of others for the learning agent, and uses empirical game-theoretic analysis to estimate payoffs for each strategy profile obtained due to the perturbation.

Xiaoming Duan, Mishel George, Rushabh Patel et al.

This paper analyzes the meeting time between a pair of pursuer and evader performing random walks on digraphs. The existing bounds on the meeting time usually work only for certain classes of walks and cannot be used to formulate optimization problems and design robotic strategies. First, by analyzing multiple random walks on a common graph as a single random walk on the Kronecker product graph, we provide the first closed-form expression for the expected meeting time in terms of the transition matrices of the moving agents. This novel expression leads to necessary and sufficient conditions for the meeting time to be finite and to insightful graph-theoretic interpretations. Second, based on the closed-form expression, we setup and study the minimization problem for the expected capture time for a pursuer/evader pair. We report theoretical and numerical results on basic case studies to show the effectiveness of the design.