Collision Avoidance Verification of Multiagent Systems with Learned Policies

• URL: http://arxiv.org/abs/2403.03314v2
• Date: Thu, 25 Apr 2024 19:12:02 GMT
• Title: Collision Avoidance Verification of Multiagent Systems with Learned Policies
• Authors: Zihao Dong, Shayegan Omidshafiei, Michael Everett,
• Abstract summary: This paper presents a backward reachability-based approach for verifying the collision avoidance properties of Multi-Agent Feedback Loops (MA-NFLs) We account for many uncertainties, making it well aligned with real-world scenarios. We demonstrate the proposed algorithm can verify collision-free properties of a MA-NFL with agents trained to imitate a collision avoidance algorithm.
• Score: 9.550601011551024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For many multiagent control problems, neural networks (NNs) have enabled promising new capabilities. However, many of these systems lack formal guarantees (e.g., collision avoidance, robustness), which prevents leveraging these advances in safety-critical settings. While there is recent work on formal verification of NN-controlled systems, most existing techniques cannot handle scenarios with more than one agent. To address this research gap, this paper presents a backward reachability-based approach for verifying the collision avoidance properties of Multi-Agent Neural Feedback Loops (MA-NFLs). Given the dynamics models and trained control policies of each agent, the proposed algorithm computes relative backprojection sets by (simultaneously) solving a series of Mixed Integer Linear Programs (MILPs) offline for each pair of agents. We account for state measurement uncertainties, making it well aligned with real-world scenarios. Using those results, the agents can quickly check for collision avoidance online by solving low-dimensional Linear Programs (LPs). We demonstrate the proposed algorithm can verify collision-free properties of a MA-NFL with agents trained to imitate a collision avoidance algorithm (Reciprocal Velocity Obstacles). We further demonstrate the computational scalability of the approach on systems with up to 10 agents.

Related papers

• Variational Autoencoders for exteroceptive perception in reinforcement learning-based collision avoidance [0.0]
  Deep Reinforcement Learning (DRL) has emerged as a promising control framework. Current DRL algorithms require disproportionally large computational resources to find near-optimal policies. This paper presents a comprehensive exploration of our proposed approach in maritime control systems.
  arXiv  Detail & Related papers  (2024-03-31T09:25:28Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• A Minimax Approach Against Multi-Armed Adversarial Attacks Detection [31.971443221041174]
  Multi-armed adversarial attacks have been shown to be highly successful in fooling state-of-the-art detectors. We propose a solution that aggregates the soft-probability outputs of multiple pre-trained detectors according to a minimax approach. We show that our aggregation consistently outperforms individual state-of-the-art detectors against multi-armed adversarial attacks.
  arXiv  Detail & Related papers  (2023-02-04T18:21:22Z)
• Scalable Task-Driven Robotic Swarm Control via Collision Avoidance and Learning Mean-Field Control [23.494528616672024]
  We use state-of-the-art mean-field control techniques to convert many-agent swarm control into classical single-agent control of distributions. Here, we combine collision avoidance and learning of mean-field control into a unified framework for tractably designing intelligent robotic swarm behavior.
  arXiv  Detail & Related papers  (2022-09-15T16:15:04Z)
• Relative Distributed Formation and Obstacle Avoidance with Multi-agent Reinforcement Learning [20.401609420707867]
  We propose a distributed formation and obstacle avoidance method based on multi-agent reinforcement learning (MARL) Our method achieves better performance regarding formation error, formation convergence rate and on-par success rate of obstacle avoidance compared with baselines.
  arXiv  Detail & Related papers  (2021-11-14T13:02:45Z)
• Increasing the Confidence of Deep Neural Networks by Coverage Analysis [71.57324258813674]
  This paper presents a lightweight monitoring architecture based on coverage paradigms to enhance the model against different unsafe inputs. Experimental results show that the proposed approach is effective in detecting both powerful adversarial examples and out-of-distribution inputs.
  arXiv  Detail & Related papers  (2021-01-28T16:38:26Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  Federated learning (FL) is vulnerable to external attacks on FL models during parameters transmissions. In this paper, we propose effective MP algorithms to combat state-of-the-art defensive aggregation mechanisms. Our experimental results demonstrate that the proposed CMP algorithms are effective and substantially outperform existing attack mechanisms.
  arXiv  Detail & Related papers  (2021-01-28T03:28:18Z)
• A Hamiltonian Monte Carlo Method for Probabilistic Adversarial Attack and Learning [122.49765136434353]
  We present an effective method, called Hamiltonian Monte Carlo with Accumulated Momentum (HMCAM), aiming to generate a sequence of adversarial examples. We also propose a new generative method called Contrastive Adversarial Training (CAT), which approaches equilibrium distribution of adversarial examples. Both quantitative and qualitative analysis on several natural image datasets and practical systems have confirmed the superiority of the proposed algorithm.
  arXiv  Detail & Related papers  (2020-10-15T16:07:26Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  Neural networks can learn complex, non- adversarial functions, and it is challenging to guarantee their correct behavior in safety-critical contexts. Many approaches exist to find failures in networks (e.g., adversarial examples), but these cannot guarantee the absence of failures. We propose an approach that integrates the optimization process into the verification procedure, achieving better performance than the naive approach.
  arXiv  Detail & Related papers  (2020-10-07T08:19:48Z)
• Certifiable Robustness to Adversarial State Uncertainty in Deep Reinforcement Learning [40.989393438716476]
  Deep Neural Network-based systems are now the state-of-the-art in many robotics tasks, but their application in safety-critical domains remains dangerous without formal guarantees on network robustness. Small perturbations to sensor inputs are often enough to change network-based decisions, which was recently shown to cause an autonomous vehicle to swerve into another lane. This work leverages research on certified adversarial robustness to develop an online certifiably robust for deep reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2020-04-11T21:36:13Z)

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.