skip to main content


This content will become publicly available on August 28, 2024

Title: 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
Award ID(s):
2208182 2038493
NSF-PAR ID:
10447854
Author(s) / Creator(s):
;
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
  1. 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
  2. Abstract

    This paper considers persistent monitoring of environmental phenomena using unmanned aerial vehicles (UAVs). The objective is to generate periodic dynamically feasible UAV trajectories that minimize the estimation uncertainty at a set of points of interest in the environment. We develop an optimization algorithm that iterates between determining the observation periods for a set of ordered points of interest and optimizing a continuous UAV trajectory to meet the required observation periods and UAV dynamics constraints. The interest-point visitation order is determined using a Traveling Salesman Problem (TSP), followed by a greedy optimization algorithm to determine the number of observations that minimizes the maximum steady-state eigenvalue of a Kalman filter estimator. Given the interest-point observation periods and visitation order, a minimum-jerk trajectory is generated from a bi-level optimization, formulated as a convex quadratically constrained quadratic program. The resulting B-spline trajectory is guaranteed to be feasible, meeting the observation duration, maximum velocity and acceleration, region enter and exit constraints. The feasible trajectories outperform existing methods by achieving comparable observability at up to 47% higher travel speeds, resulting in lower maximum estimation uncertainty.

     
    more » « less
  3. null (Ed.)
    Many methods in learning from demonstration assume that the demonstrator has knowledge of the full environment. However, in many scenarios, a demonstrator only sees part of the environment and they continuously replan as they gather information. To plan new paths or to reconstruct the environment, we must consider the visibility constraints and replanning process of the demonstrator, which, to our knowledge, has not been done in previous work. We consider the problem of inferring obstacle configurations in a 2D environment from demonstrated paths for a point robot that is capable of seeing in any direction but not through obstacles. Given a set of survey points, which describe where the demonstrator obtains new information, and a candidate path, we con-struct a Constraint Satisfaction Problem (CSP) on a cell decomposition of the environment. We parameterize a set of obstacles corresponding to an assignment from the CSP and sample from the set to find valid environments. We show that there is a probabilistically-complete, yet not entirely tractable, algorithm that can guarantee novel paths in the space are unsafe or possibly safe. We also present an incomplete, but empirically-successful, heuristic-guided algorithm that we apply in our experiments to 1) planning novel paths and 2) recovering a probabilistic representation of the environment. 
    more » « less
  4. null (Ed.)
    Location-Based Services are often used to find proximal Points of Interest PoI - e.g., nearby restaurants and museums, police stations, hospitals, etc. - in a plethora of applications. An important recently addressed variant of the problem not only considers the distance/proximity aspect, but also desires semantically diverse locations in the answer-set. For instance, rather than picking several close-by attractions with similar features - e.g., restaurants with similar menus; museums with similar art exhibitions - a tourist may be more interested in a result set that could potentially provide more diverse types of experiences, for as long as they are within an acceptable distance from a given (current) location. Towards that goal, in this work we propose a novel approach to efficiently retrieve a path that will maximize the semantic diversity of the visited PoIs that are within distance limits along a given road network. We introduce a novel indexing structure - the Diversity Aggregated R-tree, based on which we devise efficient algorithms to generate the answer-set - i.e., the recommended locations among a set of given PoIs - relying on a greedy search strategy. Our experimental evaluations conducted on real datasets demonstrate the benefits of proposed methodology over the baseline alternative approaches. 
    more » « less
  5. 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