Reachable Polyhedral Marching (RPM): An Exact Analysis Tool for Deep-Learned Control Systems

• URL: http://arxiv.org/abs/2210.08339v1
• Date: Sat, 15 Oct 2022 17:15:53 GMT
• Title: Reachable Polyhedral Marching (RPM): An Exact Analysis Tool for Deep-Learned Control Systems
• Authors: Joseph A. Vincent and Mac Schwager
• Abstract summary: We present a tool for computing exact forward and backward reachable sets of deep neural networks with rectified linear unit (ReLU) activation. We then develop algorithms using this tool to compute invariant sets and regions of attraction (ROAs) for control systems with neural networks in the feedback loop.
• Score: 20.595032143044506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a tool for computing exact forward and backward reachable sets of deep neural networks with rectified linear unit (ReLU) activation. We then develop algorithms using this tool to compute invariant sets and regions of attraction (ROAs) for control systems with neural networks in the feedback loop. Our algorithm is unique in that it builds the reachable sets by incrementally enumerating polyhedral regions in the input space, rather than iterating layer-by-layer through the network as in other methods. When performing safety verification, if an unsafe region is found, our algorithm can return this result without completing the full reachability computation, thus giving an anytime property that accelerates safety verification. Furthermore, we introduce a method to accelerate the computation of ROAs in the case that deep learned components are homeomorphisms, which we find is surprisingly common in practice. We demonstrate our tool in several test cases. We compute a ROA for a learned van der Pol oscillator model. We find a control invariant set for a learned torque-controlled pendulum model. We also verify specific safety properties for multiple deep networks related to the ACAS Xu aircraft collision advisory system. Finally, we apply our algorithm to find ROAs for an image-based aircraft runway taxi problem. Algorithm source code: https://github.com/StanfordMSL/Neural-Network-Reach .

Related papers

• Partial End-to-end Reinforcement Learning for Robustness Against Modelling Error in Autonomous Racing [0.0]
  This paper addresses the issue of increasing the performance of reinforcement learning (RL) solutions for autonomous racing cars. We propose a partial end-to-end algorithm that decouples the planning and control tasks. By leveraging the robustness of a classical controller, our partial end-to-end driving algorithm exhibits better robustness towards model mismatches than standard end-to-end algorithms.
  arXiv  Detail & Related papers  (2023-12-11T14:27:10Z)
• Attribution Patching Outperforms Automated Circuit Discovery [3.8695554579762814]
  We show that a simple method based on attribution patching outperforms all existing methods. We apply a linear approximation to activation patching to estimate the importance of each edge in the computational subgraph.
  arXiv  Detail & Related papers  (2023-10-16T12:34:43Z)
• 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)
• Pathfinding Neural Cellular Automata [23.831530224401575]
  Pathfinding is an important sub-component of a broad range of complex AI tasks, such as robot path planning, transport routing, and game playing. We hand-code and learn models for Breadth-First Search (BFS), i.e. shortest path finding. We present a neural implementation of Depth-First Search (DFS), and outline how it can be combined with neural BFS to produce an NCA for computing diameter of a graph. We experiment with architectural modifications inspired by these hand-coded NCAs, training networks from scratch to solve the diameter problem on grid mazes while exhibiting strong ability generalization
  arXiv  Detail & Related papers  (2023-01-17T11:45:51Z)
• Backdoor Attack Detection in Computer Vision by Applying Matrix Factorization on the Weights of Deep Networks [6.44397009982949]
  We introduce a novel method for backdoor detection that extracts features from pre-trained DNN's weights. In comparison to other detection techniques, this has a number of benefits, such as not requiring any training data. Our method outperforms the competing algorithms in terms of efficiency and is more accurate, helping to ensure the safe application of deep learning and AI.
  arXiv  Detail & Related papers  (2022-12-15T20:20:18Z)
• Automated Reachability Analysis of Neural Network-Controlled Systems via Adaptive Polytopes [2.66512000865131]
  We develop a new approach for over-approximating the reachable sets of neural network dynamical systems using adaptive template polytopes. We illustrate the utility of the proposed approach in the reachability analysis of linear systems driven by neural network controllers.
  arXiv  Detail & Related papers  (2022-12-14T23:49:53Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Physics-informed Neural Networks-based Model Predictive Control for Multi-link Manipulators [0.0]
  We discuss nonlinear model predictive control (NMPC) for multi-body dynamics via physics-informed machine learning methods. We present the idea of enhancing PINNs by adding control actions and initial conditions as additional network inputs. We present our results using our PINN-based MPC to solve a tracking problem for a complex mechanical system.
  arXiv  Detail & Related papers  (2021-09-22T15:31:24Z)
• Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems [79.67879934935661]
  We study the problem of system identification and adaptive control of unknown ARX systems. We provide finite-time learning guarantees for the ARX systems under both open-loop and closed-loop data collection.
  arXiv  Detail & Related papers  (2021-08-26T18:00:00Z)
• Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysis [65.31074639627226]
  Principal component analysis (PCA) is a technique for extracting the linear structure of a dataset. We propose the deployment of PCA over a multi-access channel based on the algorithm of gradient descent. Over-the-air aggregation is adopted to reduce the multi-access latency, giving the name over-the-air PCA.
  arXiv  Detail & Related papers  (2021-04-20T16:28:33Z)
• Composable Learning with Sparse Kernel Representations [110.19179439773578]
  We present a reinforcement learning algorithm for learning sparse non-parametric controllers in a Reproducing Kernel Hilbert Space. We improve the sample complexity of this approach by imposing a structure of the state-action function through a normalized advantage function. We demonstrate the performance of this algorithm on learning obstacle-avoidance policies in multiple simulations of a robot equipped with a laser scanner while navigating in a 2D environment.
  arXiv  Detail & Related papers  (2021-03-26T13:58:23Z)
• Phase Retrieval using Expectation Consistent Signal Recovery Algorithm based on Hypernetwork [73.94896986868146]
  Phase retrieval is an important component in modern computational imaging systems. Recent advances in deep learning have opened up a new possibility for robust and fast PR. We develop a novel framework for deep unfolding to overcome the existing limitations.
  arXiv  Detail & Related papers  (2021-01-12T08:36:23Z)
• 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)
• Risk-Averse MPC via Visual-Inertial Input and Recurrent Networks for Online Collision Avoidance [95.86944752753564]
  We propose an online path planning architecture that extends the model predictive control (MPC) formulation to consider future location uncertainties. Our algorithm combines an object detection pipeline with a recurrent neural network (RNN) which infers the covariance of state estimates. The robustness of our methods is validated on complex quadruped robot dynamics and can be generally applied to most robotic platforms.
  arXiv  Detail & Related papers  (2020-07-28T07:34:30Z)
• DHP: Differentiable Meta Pruning via HyperNetworks [158.69345612783198]
  This paper introduces a differentiable pruning method via hypernetworks for automatic network pruning. Latent vectors control the output channels of the convolutional layers in the backbone network and act as a handle for the pruning of the layers. Experiments are conducted on various networks for image classification, single image super-resolution, and denoising.
  arXiv  Detail & Related papers  (2020-03-30T17:59:18Z)
• AutoML-Zero: Evolving Machine Learning Algorithms From Scratch [76.83052807776276]
  We show that it is possible to automatically discover complete machine learning algorithms just using basic mathematical operations as building blocks. We demonstrate this by introducing a novel framework that significantly reduces human bias through a generic search space. We believe these preliminary successes in discovering machine learning algorithms from scratch indicate a promising new direction in the field.
  arXiv  Detail & Related papers  (2020-03-06T19:00:04Z)
• Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond [171.07853346630057]
  Linear relaxation based perturbation analysis (LiRPA) for neural networks has become a core component in robustness verification and certified defense. We develop an automatic framework to enable perturbation analysis on any neural network structures. We demonstrate LiRPA based certified defense on Tiny ImageNet and Downscaled ImageNet.
  arXiv  Detail & Related papers  (2020-02-28T18:47:43Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

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.