Real-Time Synthesis of Robust Controlled Invariant Sets for Monotone Systems

• URL: http://arxiv.org/abs/2609.14115v1
• Date: Sat, 12 Sep 2026 19:31:38 GMT
• Title: Real-Time Synthesis of Robust Controlled Invariant Sets for Monotone Systems
• Abstract summary: Control of autonomous systems requires formal safety certificates, such as controlled invariant sets, that must be computed online as conditions change.<n>In particular, lazy fixed-point algorithms exploit monotonicity and track only the antichain basis of the set.<n>We introduce a threshold-function reformulation in which a lower-closed set on a d-dimensional grid is represented by its column heights along a designated axis.
• Score: 1.233704313688752
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Safety-critical control of autonomous systems requires formal safety certificates, such as controlled invariant sets, that must be computed online as conditions change. Although standard synthesis algorithms scale poorly with state dimension, monotone dynamical systems with lower-closed safety specifications allow for accelerated computation of controlled invariant sets. In particular, lazy fixed-point algorithms exploit monotonicity and track only the antichain basis of the set. However, membership tests and redundancy checks against an evolving basis remain major bottlenecks. We introduce a threshold-function reformulation in which a lower-closed set on a d-dimensional grid is represented by its column heights along a designated axis. This reformulates the greatest-fixed-point iteration as independent one-dimensional binary searches, one per grid column, yielding an embarrassingly parallel iteration with asymptotically lower computational complexity than the lazy fixed-point algorithm. Experiments synthesize invariant sets on 3D grids with 10^9 cells in under 50 ms and 10^14 cells in under two minutes. We further demonstrate online re-synthesis in a safety-informed model predictive controller example.

Related papers

• Quantum-Inspired Hybrid Neural Networks for Neural Decoding: A Controlled Ablation Study of Learnable Quantum Sidecar Integration [5.2726003549534655]
  We study parameterized quantum circuits (PQCs) integrated as residual sidecar modules within a ResNet-50 backbone for neural population decoding.<n>We compare four model variants: baseline, quantum sidecar with frozen input projection, quantum sidecar with backbone-gradient-trained projection, and a measurement-guided variant that aligns angle encodings with circuit measurement outcomes.
  arXiv  Detail & Related papers  (2026-08-23T15:55:43Z)
• A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems [14.967168108174464]
  We study the natural prerequisite of online prediction.<n>Our goal is to achieve sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics.
  arXiv  Detail & Related papers  (2026-07-02T11:24:08Z)
• Differentiable Invariant Sets for Hybrid Limit Cycles with Application to Legged Robots [4.9489833968237065]
  We extend methods for overapproximating reachable sets of continuous systems using parametric embeddings to compute a forward-invariant set around the nominal trajectory of a bipedal robot.<n>We verify this condition on the bipedal walker model numerically using immrax, a JAX-based library for parametric reachable set, and use it within a bi-level optimization framework to design a tracking controller.
  arXiv  Detail & Related papers  (2026-04-06T19:14:02Z)
• Minimal Information Control Invariance via Vector Quantization [2.094349987888854]
  We study how many distinct control signals are needed to render a compact set forward invariant under sampled-data control.<n>We propose a vector-quantized autoencoder that jointly learns a state-space partition and a finite control codebook.<n>We empirically characterize the minimum sensing resolution compatible with safe operation.
  arXiv  Detail & Related papers  (2026-04-03T15:53:07Z)
• Cryptanalysis of a Lightweight RFID Authentication Protocol Based on a Variable Matrix Encryption Algorithm [0.7782106464483302]
  Two-way RFID authentication protocol based on the AM-SUEO-DBLTKM variable matrix encryption algorithm was proposed for low-cost mobile RFID systems.<n>In this paper, we show that the protocol has structural weaknesses.
  arXiv  Detail & Related papers  (2026-03-30T11:35:40Z)
• BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
  We propose Bit-Plane Decomposition Quantization (BPDQ), which constructs a variable quantization grid via bit-planes and scalar coefficients.<n>BPDQ enables serving Qwen2.5-72B on a single GTX 3090 with 83.85% GSM8K accuracy (vs. 90.83% at 16-bit)
  arXiv  Detail & Related papers  (2026-02-04T02:54:37Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  We study a class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We prove that controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees. We analyze two important settings where a mere spectral norm control turns out to be sufficient.
  arXiv  Detail & Related papers  (2022-02-13T07:12:02Z)
• Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
  Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. We propose Linformer and Informer to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention.
  arXiv  Detail & Related papers  (2021-12-10T06:58:05Z)
• Learning Stabilizing Controllers for Unstable Linear Quadratic Regulators from a Single Trajectory [85.29718245299341]
  We study linear controllers under quadratic costs model also known as linear quadratic regulators (LQR) We present two different semi-definite programs (SDP) which results in a controller that stabilizes all systems within an ellipsoid uncertainty set. We propose an efficient data dependent algorithm -- textsceXploration -- that with high probability quickly identifies a stabilizing controller.
  arXiv  Detail & Related papers  (2020-06-19T08:58:57Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  Bilinear pooling achieves great success in fine-grained visual recognition (FGVC) Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features. We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
  arXiv  Detail & Related papers  (2020-03-30T08:40:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.