BURNS: Backward Underapproximate Reachability for Neural-Feedback-Loop Systems

• URL: http://arxiv.org/abs/2505.03643v1
• Date: Tue, 06 May 2025 15:50:43 GMT
• Title: BURNS: Backward Underapproximate Reachability for Neural-Feedback-Loop Systems
• Authors: Chelsea Sidrane, Jana Tumova,
• Abstract summary: We introduce an algorithm for computing underapproximate backward reachable sets of nonlinear discrete time neural feedback loops.<n>We then use the backward reachable sets to check goal-reaching properties.<n>Our work expands the class of properties that can be verified for learning-enabled systems.
• Score: 8.696305200911455
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Learning-enabled planning and control algorithms are increasingly popular, but they often lack rigorous guarantees of performance or safety. We introduce an algorithm for computing underapproximate backward reachable sets of nonlinear discrete time neural feedback loops. We then use the backward reachable sets to check goal-reaching properties. Our algorithm is based on overapproximating the system dynamics function to enable computation of underapproximate backward reachable sets through solutions of mixed-integer linear programs. We rigorously analyze the soundness of our algorithm and demonstrate it on a numerical example. Our work expands the class of properties that can be verified for learning-enabled systems.

Related papers

• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learning is a novel unified framework for learning with neural networks "over time" It is based on differential equations that: (i) can be integrated without the need of external software solvers; (ii) generalize the well-established notion of gradient-based learning in feed-forward and recurrent networks; (iii) open to novel perspectives.
  arXiv  Detail & Related papers  (2024-09-18T14:57:13Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Interval Reachability of Nonlinear Dynamical Systems with Neural Network Controllers [5.543220407902113]
  This paper proposes a computationally efficient framework, based on interval analysis, for rigorous verification of nonlinear continuous-time dynamical systems with neural network controllers. Inspired by mixed monotone theory, we embed the closed-loop dynamics into a larger system using an inclusion function of the neural network and a decomposition function of the open-loop system. We show that one can efficiently compute hyper-rectangular over-approximations of the reachable sets using a single trajectory of the embedding system.
  arXiv  Detail & Related papers  (2023-01-19T06:46:36Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Tree-Based Adaptive Model Learning [62.997667081978825]
  We extend the Kearns-Vazirani learning algorithm to handle systems that change over time. We present a new learning algorithm that can reuse and update previously learned behavior, implement it in the LearnLib library, and evaluate it on large examples.
  arXiv  Detail & Related papers  (2022-08-31T21:24:22Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification. We design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-09T02:33:36Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Reachable Polyhedral Marching (RPM): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Components [20.595032143044506]
  We present a method for computing exact reachable sets for deep neural networks with rectified linear unit (ReLU) activation. Our algorithm can compute both forward and backward reachable sets for a ReLU network iterated over multiple time steps. We demonstrate our algorithm on safety verification of the ACAS Xu aircraft advisory system.
  arXiv  Detail & Related papers  (2020-11-23T18:35:53Z)
• Active Learning for Identification of Linear Dynamical Systems [12.056495277232118]
  We show a finite time bound estimation rate our algorithm attains. We analyze several examples where our algorithm provably improves over rates obtained by playing noise.
  arXiv  Detail & Related papers  (2020-02-02T21:30:38Z)

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.