Search

Reach-Avoid-Stay (RAS) optimal control enables systems such as robots and air taxis to reach their targets, avoid obstacles, and stay near the target. However, current methods for RAS often struggle with handling complex, dynamic environments and scaling to high-dimensional systems. While reinforcement learning (RL)-based reachability analysis addresses these challenges, it has yet to tackle the RAS problem. In this paper, we propose a two-step deep deterministic policy gradient (DDPG) method to extend RL-based reachability method to solve RAS problems. First, we train a function that characterizes the maximal robust control invariant set within the target set, where the system can safely stay, along with its corresponding policy. Second, we train a function that defines the set of states capable of safely reaching the robust control invariant set, along with its corresponding policy. We prove that this method results in the maximal robust RAS set in the absence of training errors and demonstrate that it enables RAS in complex environments, scales to high-dimensional systems, and achieves higher success rates for the RAS task compared to previous methods, validated through one simulation and two high-dimensional experiments.

We provide a programmable recursive algorithm for the $\mathbb{S}_n$-representations on the cohomology of the moduli spaces $\overline{\mathcal M}_{0,n}$ of $n$-pointed stable curves of genus 0. As an application, we find explicit inductive and asymptotic formulas for the invariant part $H^*(\overline{\mathcal M}_{0,n}/\mathbb{S}_n)$ and prove that its Poincar\'e polynomial is asymptotically log-concave. Based on numerical computations with our algorithm, we further conjecture that the sequence $\{H^{2k}(\overline{\mathcal M}_{0,n})\}$ of $\mathbb{S}_n$-modules is equivariantly log-concave., Comment: 38 pages

We propose a new reachability learning framework for high-dimensional nonlinear systems, focusing on reach-avoid problems. These problems require computing the reach-avoid set, which ensures that all its elements can safely reach a target set despite any disturbance within pre-specified bounds. Our framework has two main parts: offline learning of a newly designed reach-avoid value function and post-learning certification. Compared to prior works, our new value function is Lipschitz continuous and its associated Bellman operator is a contraction mapping, both of which improve the learning performance. To ensure deterministic guarantees of our learned reach-avoid set, we introduce two efficient post-learning certification methods. Both methods can be used online for real-time local certification or offline for comprehensive certification. We validate our framework in a 12-dimensional crazyflie drone racing hardware experiment and a simulated 10-dimensional highway takeover example., Comment: Submitted, under review

We show that regular semisimple Hessenberg varieties can have moduli. To be precise, suppose $X$ is a regular semisimple Hessenberg variety of codimension 1 in the flag variety $G/B$, where $G$ is a simple algebraic group of rank $r$ over $\mathbb{C}$ and $B$ is a Borel subgroup. We show that the space $\mathrm{H}^1(X,TX)$ of first order deformations of $X$ has dimension $r-1$ except in type $A_2$. (In type $A_2$, the Hessenberg varieties in question are all isomorphic to the permutohedral toric surface, and $\mathrm{dim}\mathrm{H}^1(X,TX)=0$.) Moreover, we show that the Kodaira-Spencer map $\mathfrak{g}\to\mathrm{H}^1(X,TX)$ is onto, that the connected component of the automorphism group of $X$ is the maximal torus of $G$, and that $\mathrm{H}^i(X,TX)=0$ for $i\geq2$. Along the way, we prove several theorems of independent interest about the cohomology of homogeneous vector bundles on $G/B$. In type $A$, we can give an even more precise statement determining when two codimension $1$ regular semisimple Hessenberg varieties in $G/B$ are isomorphic. We also compute the automorphism groups explicitly in type $A_{n-1}$ in the terms of stabilizer subgroups of the action of the symmetric group $S_n$ on the moduli space $M_{0,n+1}$ of smooth genus $0$ curves with $n+1$ marked points. Using this, we describe the moduli stack of the regular semisimple Hessenberg varieties $X$ explicitly as a quotient stack of $M_{0,n+1}$. We prove several analogous results for Hessenberg varieties in generalized flag varieties $G/P$, where $P$ is a parabolic subgroup of $G$. In type $A$, these results are used in the proofs of the results for $G/B$, but they are also independently interesting because the associated moduli stacks are related directly to the action of $S_n$ on $M_{0,n}$., Comment: 48 pages, minor changes

Control invariant sets are crucial for various methods that aim to design safe control policies for systems whose state constraints must be satisfied over an indefinite time horizon. In this article, we explore the connections among reachability, control invariance, and Control Barrier Functions (CBFs). Unlike prior formulations based on backward reachability concepts, by examining a forward reachability problem, we are able to establish a strong link between these three concepts. First, our findings show that the inevitable Forward Reachable Tube (FRT), which is the set of states such that every trajectory reaching the FRT must have passed through a given initial set of states, is precisely this initial set of states itself if it is a robust control invariant set with a differentiable boundary. We highlight that this statement may not hold if the boundary is not differentiable. Next, we formulate a differential game between the control and disturbance, where the inevitable FRT is characterized by the zero-superlevel set of the value function. By incorporating a discount factor in the cost function of the game, the barrier constraint of the CBF naturally arises as the constraint that is imposed on the optimal control policy. Combining these results, the value function of our FRT formulation serves as a CBF-like function, and conversely, any valid CBF is also a forward reachability value function inside the control invariant set, thereby revealing the inverse optimality of the CBF. This strong link we establish between the reachability problem and the barrier constraint, while guaranteeing the continuity of the value function, is not achievable by previous backward reachability-based formulations. As such, our work fills a crucial gap in the existing literature that is vital for constructing valid CBFs to ensure safety., Comment: The first two authors contributed equally to this work

Recently, Masuda-Sato and Precup-Sommers independently proved an LLT version of the Shareshian-Wachs conjecture which says that the Frobenius characteristics of the cohomology of the twin manifolds of regular semisimple Hessenberg varieties are unicellular LLT polynomials. The purpose of this paper is to study the geometry of twin manifolds and we prove that they are related by explicit blowups and fiber bundle maps. Upon taking their cohomology, we obtain a direct proof of the modular law which establishes the LLT Shareshian-Wachs conjecture., Comment: 29 pages

Autonomous vehicles (AVs) must share the driving space with other drivers and often employ conservative motion planning strategies to ensure safety. These conservative strategies can negatively impact AV's performance and significantly slow traffic throughput. Therefore, to avoid conservatism, we design an interaction-aware motion planner for the ego vehicle (AV) that interacts with surrounding vehicles to perform complex maneuvers in a locally optimal manner. Our planner uses a neural network-based interactive trajectory predictor and analytically integrates it with model predictive control (MPC). We solve the MPC optimization using the alternating direction method of multipliers (ADMM) and prove the algorithm's convergence. We provide an empirical study and compare our method with a baseline heuristic method.

A key challenge in fast ground robot navigation in 3D terrain is balancing robot speed and safety. Recent work has shown that 2.5D maps (2D representations with additional 3D information) are ideal for real-time safe and fast planning. However, the prevalent approach of generating 2D occupancy grids through raytracing makes the generated map unsafe to plan in, due to inaccurate representation of unknown space. Additionally, existing planners such as MPPI do not consider speeds in known free and unknown space separately, leading to slower overall plans. The RAMP pipeline proposed here solves these issues using new mapping and planning methods. This work first presents ground point inflation with persistent spatial memory as a way to generate accurate occupancy grid maps from classified pointclouds. Then we present an MPPI-based planner with embedded variability in horizon, to maximize speed in known free space while retaining cautionary penetration into unknown space. Finally, we integrate this mapping and planning pipeline with risk constraints arising from 3D terrain, and verify that it enables fast and safe navigation using simulations and hardware demonstrations., Comment: 7 pages submitted to ICRA 2023

We introduce generalized Hessenberg varieties and establish basic facts. We show that the Tymoczko action of the symmetric group $S_n$ on the cohomology of Hessenberg varieties extends to generalized Hessenberg varieties and that natural morphisms among them preserve the action. By analyzing natural morphisms and birational maps among generalized Hessenberg varieties, we give an elementary proof of the Shareshian-Wachs conjecture. Moreover we present a natural generalization of the Shareshian-Wachs conjecture that involves generalized Hessenberg varieties and provide an elementary proof. As a byproduct, we propose a generalized Stanley-Stembridge conjecture for weighted graphs. Our investigation into the birational geometry of generalized Hessenberg varieties enables us to modify them into much simpler varieties like projective spaces or permutohedral varieties by explicit sequences of blowups or projective bundle maps. Using this, we provide two algorithms to compute the $S_n$-representations on the cohomology of generalized Hessenberg varieties. As an application, we compute representations on the low degree cohomology of some Hessenberg varieties., Comment: 39 pages

In this paper, we consider the infinite-horizon reach-avoid zero-sum game problem, where the goal is to find a set in the state space, referred to as the reach-avoid set, such that the system starting at a state therein could be controlled to reach a given target set without violating constraints under the worst-case disturbance. We address this problem by designing a new value function with a contracting Bellman backup, where the super-zero level set, i.e., the set of states where the value function is evaluated to be non-negative, recovers the reach-avoid set. Building upon this, we prove that the proposed method can be adapted to compute the viability kernel, or the set of states which could be controlled to satisfy given constraints, and the backward reachable set, or the set of states that could be driven towards a given target set. Finally, we propose to alleviate the curse of dimensionality issue in high-dimensional problems by extending Conservative Q-Learning, a deep reinforcement learning technique, to learn a value function such that the super-zero level set of the learned value function serves as a (conservative) approximation to the reach-avoid set. Our theoretical and empirical results suggest that the proposed method could learn reliably the reach-avoid set and the optimal control policy even with neural network approximation.

The moduli space $\overline{\mathcal{M}}_{0,n}$ of $n$ pointed stable curves of genus $0$ admits an action of the symmetric group $S_n$ by permuting the marked points. We provide a closed formula for the character of the $S_n$-action on the cohomology of $\overline{\mathcal{M}}_{0,n}$. This is achieved by studying wall crossings of the moduli spaces of quasimaps which provide us with a new inductive construction of $\overline{\mathcal{M}}_{0,n}$, equivariant with respect to the symmetric group action. Moreover we prove that $H^{2k}(\overline{\mathcal{M}}_{0,n})$ for $k\le 3$ and $H^{2k}(\overline{\mathcal{M}}_{0,n})\oplus H^{2k-2}(\overline{\mathcal{M}}_{0,n})$ for any $k$ are permutation representations. Our method works for related moduli spaces as well and we provide a closed formula for the character of the $S_n$-representation on the cohomology of the Fulton-MacPherson compactification $\mathbb{P}^1[n]$ of the configuration space of $n$ points on $\mathbb{P}^1$ and more generally on the cohomology of the moduli space $\overline{\mathcal{M}}_{0,n}(\mathbb{P}^{m-1},1)$ of stable maps., Comment: 62 pages

Collaboration between interconnected cyber-physical systems is becoming increasingly pervasive. Time-delays in communication channels between such systems are known to induce catastrophic failure modes, like high frequency oscillations in robotic manipulators in bilateral teleoperation or string instability in platoons of autonomous vehicles. This paper considers nonlinear time-delay systems representing coupled robotic agents, and proposes controllers that are robust to time-varying communication delays. We introduce approximations that allow the delays to be considered as implicit control inputs themselves, and formulate the problem as a zero-sum differential game between the stabilizing controllers and the delays acting adversarially. The ensuing optimal control law is finally compared to known results from Lyapunov-Krasovskii based approaches via numerical experiments., Comment: 7 pages, 5 figures, Submitted to IEEE Control Systems Letters

This paper presents Lax formulae for solving the following optimal control problems: minimize the maximum (or the minimum) cost over a time horizon, while satisfying a state constraint. We present a viscosity theory, and by applying the theory to the Hamilton-Jacobi (HJ) equations, these Lax formulae are derived. A numerical algorithm for the Lax formulae is presented: under certain conditions, this algorithm's computational complexity is polynomial in the dimension of the state. For each class of optimal control problem, an example demonstrates the use and performance of the Lax formulae.

This paper presents Hamilton-Jacobi (HJ) formulations for two classes of two-player zero-sum games: one with a maximum cost value over time, and one with a minimum cost value over time. In the zero-sum game setting, player A minimizes the given cost while satisfying state constraints, and player B wants to prevent player A's success. For each class of problems, this paper presents two HJ equations: one for time-varying dynamics, cost, and state constraint; the other for time-invariant dynamics, cost, and state constraint. Utilizing the HJ equations, the optimal control for each player is analyzed, and a numerical algorithm is presented to compute the solution to the HJ equations. A two-dimensional water system is introduced as an example to demonstrate the proposed HJ framework.

This paper investigates a Hamilton-Jacobi (HJ) analysis to solve finite-horizon optimal control problems for high-dimensional systems. Although grid-based methods, such as the level-set method [1], numerically solve a general class of HJ partial differential equations, the computational complexity is exponential in the dimension of the continuous state. To manage this computational complexity, methods based on Lax-Hopf theory have been developed for the state-unconstrained optimal control problem under certain assumptions, such as affine dynamics and state-independent stage cost. Based on the Lax formula [2], this paper proposes an HJ formula for the state-constrained optimal control problem for nonlinear systems. We call this formula \textit{the generalized Lax formula} for the optimal control problem. The HJ formula provides both the optimal cost and an optimal control signal. We also provide an efficient computational method for a class of problems for which the dynamics is affine in the state, and for which the stage and terminal cost, as well as the state constraints, are convex in the state. This class of problems does not require affine dynamics and convex stage cost in the control. This paper also provides three practical examples.

This paper works towards unifying two popular approaches in the safety control community: Hamilton-Jacobi (HJ) reachability and Control Barrier Functions (CBFs). HJ Reachability has methods for direct construction of value functions that provide safety guarantees and safe controllers, however the online implementation can be overly conservative and/or rely on chattering bang-bang control. The CBF community has methods for safe-guarding controllers in the form of point-wise optimization using quadratic programs (CBF-QP), where the CBF-based safety certificate is used as a constraint. However, finding a valid CBF for a general dynamical system is challenging. This paper unifies these two methods by introducing a new reachability formulation inspired by the structure of CBFs to construct a Control Barrier-Value Function (CBVF). We verify that CBVF is a viscosity solution to a novel Hamilton-Jacobi-Isaacs Variational Inequality and preserves the same safety guarantee as the original reachability formulation. Finally, inspired by the CBF-QP, we propose a QP-based online control synthesis for systems affine in control and disturbance, whose solution is always the CBVF's optimal control signal robust to bounded disturbance. We demonstrate the benefit of using the CBVFs for double-integrator and Dubins car systems by comparing it to previous methods., Comment: IEEE CDC 2021

Cuprates, a member of high-Tc superconductors, have been on the long-debate on their superconducting mechanism, so that predicting the critical temperature of cuprates still remains elusive. Herein, using machine learning and first principle calculations, we predict the maximum superconducting transition temperature (Tc,max) of hole-doped cuprates and suggest the explicit functional form for Tc,max with the root-mean-square-error of 3.705 K and the coefficient of determination R2 of 0.969. We employed two machine learning models; one is a parametric brute force searching method and another is a non-parametric random forest regression model. We have found that material dependent parameters such as the Bader charge of apical oxygen, the bond strength between apical atoms, and the number of superconducting layers are important features to estimate Tc,max. Furthermore, we predict the Tc,max of hypothetical cuprates generated by replacing apical cations with other elements. When Ga is an apical cation, the predicted Tc,max is the highest among the hypothetical structures with 71, 117, and 131 K for one, two, and three CuO2 layers, respectively. These findings suggest that machine learning could guide the design of new high-Tc superconductors in the future.

A classic reachability problem for safety of dynamic systems is to compute the set of initial states from which the state trajectory is guaranteed to stay inside a given constraint set over a given time horizon. In this paper, we leverage existing theory of reachability analysis and risk measures to devise a risk-sensitive reachability approach for safety of stochastic dynamic systems under non-adversarial disturbances over a finite time horizon. Specifically, we first introduce the notion of a risk-sensitive safe set as a set of initial states from which the risk of large constraint violations can be reduced to a required level via a control policy, where risk is quantified using the Conditional Value-at-Risk (CVaR) measure. Second, we show how the computation of a risk-sensitive safe set can be reduced to the solution to a Markov Decision Process (MDP), where cost is assessed according to CVaR. Third, leveraging this reduction, we devise a tractable algorithm to approximate a risk-sensitive safe set, and provide theoretical arguments about its correctness. Finally, we present a realistic example inspired from stormwater catchment design to demonstrate the utility of risk-sensitive reachability analysis. In particular, our approach allows a practitioner to tune the level of risk sensitivity from worst-case (which is typical for Hamilton-Jacobi reachability analysis) to risk-neutral (which is the case for stochastic reachability analysis).