An official website of the United States government
This paper presents a method to lower-bound the distance of closest approach between points on an unsafe set and points along system trajectories. Such a minimal distance is a quantifiable and interpretable certificate of safety of trajectories, as compared to prior art in barrier and density methods which offers a binary indication of safety/unsafety. The distance estimation problem is converted into a infinitedimensional linear program in occupation measures based on existing work in peak estimation and optimal transport. The moment-SOS hierarchy is used to obtain a sequence of lower bounds obtained through solving semidefinite programs in increasing size, and these lower bounds will converge to the true minimal distance as the degree approaches infinity under mild conditions (e.g. Lipschitz dynamics, compact sets).
more »
« less
Bounding the Distance to Unsafe Sets With Convex Optimization
This work proposes an algorithm to bound the minimum distance between points on trajectories of a dynamical system and points on an unsafe set. Prior work on certifying safety of trajectories includes barrier and density methods, which do not provide a margin of proximity to the unsafe set in terms of distance. The distance estimation problem is relaxed to a Monge-Kantorovich-type optimal transport problem based on existing occupation-measure methods of peak estimation. Specialized programs may be developed for polyhedral norm distances (e.g. L1 and Linfinity) and for scenarios where a shape is traveling along trajectories (e.g. rigid body motion). The distance estimation problem will be correlatively sparse when the distance objective is separable.
more »
« less
- PAR ID:
- 10447854
- Date Published:
- Journal Name:
- IEEE Transactions on Automatic Control
- ISSN:
- 0018-9286
- Page Range / eLocation ID:
- 1 to 15
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present a scalable algorithm for learning parametric constraints in high dimensions from safe expert demonstrations. To reduce the ill-posedness of the constraint recovery problem, our method uses hit-and-run sampling to generate lower cost, and thus unsafe, trajectories. Both safe and unsafe trajectories are used to obtain a representation of the unsafe set that is compatible with the data by solving an integer program in that representationβs parameter space. Our method can either leverage a known parameterization or incrementally grow a parameterization while remaining consistent with the data, and we provide theoretical guarantees on the conservativeness of the recovered unsafe set. We evaluate our method on high-dimensional constraints for high-dimensional systems by learning constraints for 7-DOF arm, quadrotor, and planar pushing examples, and show that our method outperforms baseline approaches.more » « less
-
We extend the learning from demonstration paradigm by providing a method for learning unknown constraints shared across tasks, using demonstrations of the tasks, their cost functions, and knowledge of the system dynamics and control constraints. Given safe demonstrations, our method uses hit-and-run sampling to obtain lower cost, and thus unsafe, trajectories. Both safe and unsafe trajectories are used to obtain a consistent representation of the unsafe set via solving an integer program. Our method generalizes across system dynamics and learns a guaranteed subset of the constraint. In addition, by leveraging a known parameterization of the constraint, we modify our method to learn parametric constraints in high dimensions. We also provide theoretical analysis on what subset of the constraint and safe set can be learnable from safe demonstrations. We demonstrate our method on linear and nonlinear system dynamics, show that it can be modified to work with suboptimal demonstrations, and that it can also be used to learn constraints in a feature space.more » « less
-
The level set estimation problem seeks to find all points in a domain ξ where the value of an unknown function π:ξββ exceeds a threshold πΌ . The estimation is based on noisy function evaluations that may be acquired at sequentially and adaptively chosen locations in ξ . The threshold value πΌ can either be explicit and provided a priori, or implicit and defined relative to the optimal function value, i.e. πΌ=(1βπ)π(π±β) for a given π>0 where π(π±β) is the maximal function value and is unknown. In this work we provide a new approach to the level set estimation problem by relating it to recent adaptive experimental design methods for linear bandits in the Reproducing Kernel Hilbert Space (RKHS) setting. We assume that π can be approximated by a function in the RKHS up to an unknown misspecification and provide novel algorithms for both the implicit and explicit cases in this setting with strong theoretical guarantees. Moreover, in the linear (kernel) setting, we show that our bounds are nearly optimal, namely, our upper bounds match existing lower bounds for threshold linear bandits. To our knowledge this work provides the first instance-dependent, non-asymptotic upper bounds on sample complexity of level-set estimation that match information theoretic lower bounds.more » « less
-
Given the historical movement trajectories of a set of individual human agents (e.g., pedestrians, taxi drivers) and a set of new trajectories claimed to be generated by a specific agent, the Human Mobility Signature Identification (HuMID) problem aims at validating if the incoming trajectories were indeed generated by the claimed agent. This problem is important in many real-world applications such as driver verification in ride-sharing services, risk analysis for auto insurance companies, and criminal identification. Prior work on identifying human mobility behaviors requires additional data from other sources besides the trajectories, e.g., sensor readings in the vehicle for driving behavior identification. However, these data might not be universally available and is costly to obtain. To deal with this challenge, in this work, we make the first attempt to match identities of human agents only from the observed location trajectory data by proposing a novel and efficient framework named Spatio-temporal Siamese Networks (ST-SiameseNet). For each human agent, we extract a set of profile and online features from his/her trajectories. We train ST-SiameseNet to predict the mobility signature similarity between each pair of agents, where each agent is represented by his/her trajectories and the extracted features. Experimental results on a real-world taxi trajectory dataset show that our proposed ST-SiamesNet can achieve an F_1 score of 0.8508, which significantly outperforms the state-of-the-art techniques.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/TAC.2023.3285862
