skip to main content

Title: Adversarial Risk via Optimal Transport and Optimal Couplings
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
IEEE Transactions on Information Theory
Page Range / eLocation ID:
6031 to 6052
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We provide faster algorithms for approximating the optimal transport distance, e.g. earth mover's distance, between two discrete probability distributions on n elements. We present two algorithms that compute couplings between marginal distributions with an expected transportation cost that is within an additive ϵ of optimal in time O(n^2/eps); one algorithm is straightforward to parallelize and implementable in depth O(1/eps). Further, we show that additional improvements on our results must be coupled with breakthroughs in algorithmic graph theory. 
    more » « less
  2. Inspection planning, the task of planning motions for a robot that enable it to inspect a set of points of interest, has applications in domains such as industrial, field, and medical robotics. Inspection planning can be computationally challenging, as the search space over motion plans grows exponentially with the number of points of interest to inspect. We propose a novel method, Incremental Random Inspection-roadmap Search (IRIS), that computes inspection plans whose length and set of successfully inspected points asymptotically converge to those of an optimal inspection plan. IRIS incrementally densifies a motion-planning roadmap using a sampling-based algorithm and performs efficient near-optimal graph search over the resulting roadmap as it is generated. We prove the resulting algorithm is asymptotically optimal under very general assumptions about the robot and the environment. We demonstrate IRIS’s efficacy on a simulated inspection task with a planar five DOF manipulator, on a simulated bridge inspection task with an Unmanned Aerial Vehicle (UAV), and on a medical endoscopic inspection task for a continuum parallel surgical robot in cluttered human anatomy. In all these systems IRIS computes higher-quality inspection plans orders of magnitudes faster than a prior state-of-the-art method. 
    more » « less
  3. Remaining Useful Life (RUL) estimation is critical in many engineering systems where proper predictive maintenance is needed to increase a unit's effectiveness and reduce time and cost of repairing. Typically for such systems, multiple sensors are normally used to monitor performance, which create difficulties for system state identification. In this paper, we develop a semi-supervised left-to-right constrained Hidden Markov Model (HMM) model, which is effective in estimating the RUL, while capturing the jumps among states in condition dynamics. In addition, based on the HMM model learned from multiple sensors, we build a Partial Observable Markov Decision Process (POMDP) to demonstrate how such RUL estimation can be effectively used for optimal preventative maintenance decision making. We apply this technique to the NASA Engine degradation data and demonstrate the effectiveness of the proposed method. 
    more » « less