More Like this

1. An STL-Based Formulation of Resilience in Cyber-Physical Systems

   https://doi.org/10.1007/978-3-031-15839-1_7  

   Chen, Hongkai; Lin, Shan; Smolka, Scott A.; Paoletti, Nicola (August 2022, Formal Modeling and Analysis of Timed Systems)

   Bogomolov, Sergiy; Parker, David (Ed.)

   Resiliency is the ability to quickly recover from a violation and avoid future violations for as long as possible. Such a property is of fundamental importance for Cyber-Physical Systems (CPS), and yet, to date, there is no widely agreed-upon formal treatment of CPS resiliency. We present an STL-based framework for reasoning about resiliency in CPS in which resiliency has a syntactic characterization in the form of an STL-based Resiliency Specification (SRS). Given an arbitrary STL formula φ, time bounds α and β, the SRS of φ, Rα,β (φ), is the STL formula ¬φU[0,α]G[0,β)φ, specifying that recovery from a violation of φ occur within time α (recoverability), and subsequently that φ be maintained for duration β (durability). These R-expressions, which are atoms in our SRS logic, can be combined using STL operators, allowing one to express composite resiliency specifications, e.g., multiple SRSs must hold simultaneously, or the system must eventually be resilient. We define a quantitative semantics for SRSs in the form of a Resilience Satisfaction Value (ReSV) function r and prove its soundness and completeness w.r.t. STL’s Boolean semantics. The r-value for Rα,β (φ) atoms is a singleton set containing a pair quantifying recoverability and durability. The r-value for a composite SRS formula results in a set of non-dominated recoverability-durability pairs, given that the ReSVs of subformulas might not be directly comparable (e.g., one subformula has superior durability but worse recoverability than another). To the best of our knowledge, this is the first multi-dimensional quantitative semantics for an STL-based logic. Two case studies demonstrate the practical utility of our approach. https://doi.org/10.1007/978-3-031-15839-1_7 

   more » « less
2. A*pex: Efficient Approximate Multi-Objective Search on Graphs

   Zhang, H.; Salzman, O.; Kumar, S.; Felner, A.; Hernandez, C.; Koenig, S. (January 2022, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS))

   In multi-objective search, edges are annotated with cost vectors consisting of multiple cost components. A path dominates another path with the same start and goal vertices iff the component-wise sum of the cost vectors of the edges of the former path is 'less than' the component-wise sum of the cost vectors of the edges of the latter path. The Pareto-optimal solution set is the set of all undominated paths from a given start vertex to a given goal vertex. Its size can be exponential in the size of the graph being searched, which makes multi-objective search time-consuming. In this paper, we therefore study how to find an approximate Pareto-optimal solution set for a user-provided vector of approximation factors. The size of such a solution set can be significantly smaller than the size of the Pareto-optimal solution set, which enables the design of approximate multi-objective search algorithms that are efficient and produce small solution sets. We present such an algorithm in this paper, called A*pex. A*pex builds on PPA*, a state-of-the-art approximate bi-objective search algorithm (where there are only two cost components) but (1) makes PPA* more efficient for bi-objective search and (2) generalizes it to multi-objective search for any number of cost components. We first analyze the correctness of A*pex and then experimentally demonstrate its efficiency advantage over existing approximate algorithms for bi- and tri-objective search. 

   more » « less
3. A Predictor-Corrector Method for Multi-objective Optimization in Fair Machine Learning

   https://doi.org/10.1109/BDCAT56447.2022.00041  

   Wang, Sean; Carr, Arielle; Xie, Sihong (December 2022, 2022 IEEE International Conference on Big Data (Big Data))

   Issues of fairness often arise in graphical neural networks used for misinformation detection. However, improving fairness can often come at the cost of reducing accuracy and vice versa. Therefore, we formulate the task of balancing accuracy and fairness as a multi-objective optimization (MOO) problem where we seek to find a set of Pareto optimal solutions. Traditional first-order approaches to solving MOO problems such as multigradient descent can be costly, especially with large neural networks. Instead, we describe a more efficient approach using the predictor-corrector method. Given an initial Pareto optimal point, this approach predicts the direction of a neighboring solution and refines this prediction using a few steps of multigradient descent. We show experimentally that this approach allows for the generation of high-quality Pareto fronts faster than baseline optimization methods. 

   more » « less
4. Enhanced multi-objective A* using balanced binary search trees

   Ren, Zhongqiang; Zhan, Richard; Sivakumar, Rathinam; Likhachev, Maxim; Choset, Howie (January 2022, Proceedings of the International Symposium on Combinatorial Search)

   NA (Ed.)

   This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a “frontier” set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude. 

   more » « less
5. Pareto Front-Diverse Batch Multi-Objective Bayesian Optimization

   https://doi.org/10.1609/aaai.v38i10.28951  

   Ahmadianshalchi, Alaleh; Belakaria, Syrine; Doppa, Janardhan Rao (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We consider the problem of multi-objective optimization (MOO) of expensive black-box functions with the goal of discovering high-quality and diverse Pareto fronts where we are allowed to evaluate a batch of inputs. This problem arises in many real-world applications including penicillin production where diversity of solutions is critical. We solve this problem in the framework of Bayesian optimization (BO) and propose a novel approach referred to as Pareto front-Diverse Batch Multi-Objective BO (PDBO). PDBO tackles two important challenges: 1) How to automatically select the best acquisition function in each BO iteration, and 2) How to select a diverse batch of inputs by considering multiple objectives. We propose principled solutions to address these two challenges. First, PDBO employs a multi-armed bandit approach to select one acquisition function from a given library. We solve a cheap MOO problem by assigning the selected acquisition function for each expensive objective function to obtain a candidate set of inputs for evaluation. Second, it utilizes Determinantal Point Processes (DPPs) to choose a Pareto-front-diverse batch of inputs for evaluation from the candidate set obtained from the first step. The key parameters for the methods behind these two steps are updated after each round of function evaluations. Experiments on multiple MOO benchmarks demonstrate that PDBO outperforms prior methods in terms of both the quality and diversity of Pareto solutions. 

   more » « less