• Probability Distributions on Partially Ordered Sets and Network Interdiction Games
      with Saurabh Amin and Patrick Jaillet. Minor revision in Mathematics of Operations Research.
      PreprintarXiv / Show Abstract

      We consider the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset’s elements and maximal chains is satisfied? In this article, we present a combinatorial algorithm to positively resolve this question. We show that this result plays a crucial role in the equilibrium analysis of a generic security game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs, and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. The first (resp. second) player seeks to maximize the value of effective (resp. interdicted) flow net the total transportation (resp. interdiction) cost. Using our existence result on posets and strict complementary slackness in linear programming, we show that the equilibrium properties of this game can be described using primal and dual solutions of a minimum cost circulation problem. Our analysis provides a new characterization of the critical network components.

    • Network Inspection for Detecting Strategic Attacks
      with Saurabh Amin and Lina Sela. Major revision in Operations Research.
      PreprintarXiv / Show Abstract

      We study the generic problem of strategic network inspection, in which a defender (inspection agency) is tasked with detecting the presence of multiple attacks in the network. The defender has access to a limited number of detectors that she can randomly position in the network to monitor its components. We address the question of determining a randomized inspection strategy with minimum number of detectors that ensures a target expected attack detection rate. To address this question, we formulate a mathematical program with constraints involving the Nash equilibria of a large-scale strategic game between the defender and attacker. We develop a novel approach to construct an approximate equilibrium strategy profile of the game by utilizing solutions of minimum set cover and maximum set packing problems. This construction can be viewed as a generalization of some of the previously known results in security games, and is scalable to large-scale networks. Importantly, by using game-theoretic and combinatorial arguments, we provide optimality guarantees of our solution to the inspection problem in terms of the number of detectors and attack detection rate. We also derive a structural result on the attack detection rate in equilibrium, which can be applied to further improve these guarantees through a column generation procedure.
    • Leveraging sUAS for Infrastructure Network Exploration and Failure Isolation
      with Saurabh Amin, Andrew C. Lee, and Andrew J. Weinert. Journal of Intelligent & Robotic Systems, April 2018.
      JournalDOI / Show Abstract

      Large-scale infrastructures are prone to simultaneous faults when struck by a natural or man-made event. The current operating procedure followed by many utilities needs improvement, both in terms of monitoring performance and time to repair. Motivated by the recent technological progress on small Unmanned Aerial Systems (sUAS), we propose a practical framework to integrate the monitoring capabilities of sUAS into standard utility repair operations. A key aspect of our framework is the use of monitoring locations for sUAS-based inspection of failures within a certain spatial zone (called a localization set). This set is defined based on the alerts from fixed sensors or customer calls. The positioning of monitoring locations is subject to several factors such as sUAS platform, network topology, and airspace restrictions. We formulate the problem of minimizing the maximum time to respond to all failures by routing repair vehicles to various localization sets and exploring these sets using sUAS. The formulation admits a natural decomposition into two sub-problems: the sUAS Network Exploration Problem (SNEP); and the Repair Vehicle Routing Problem (RVRP). Standard solvers can be used to solve the RVRP in a scalable manner; however, solving the SNEP for each localization set can be computationally challenging. To address this limitation, we propose a set cover based heuristic to approximately solve the SNEP. We implement the overall framework on a benchmark network.
    • Designing Network Inspection Operations Using Imperfect Diagnostic Information
      with Saurabh Amin, Steven B. Link, and Georgia Perakis. Working paper targeted for Management Science.
    • Uncertainty-Aware Routing of Aerial Sensors for Infrastructure Damage Inspection
      with Saurabh Amin, Cynthia Barnhart, Jeremy Justice, and Andrew C. Lee. Working paper targeted for Operations Research.
    • A Network Monitoring Game with Heterogeneous Component Criticality Levels
      with Saurabh Amin, Jezdimir Milošević, and Henrik Sandberg. 58th IEEE Conference on Decision and Control (CDC).
    • Integration of sUAS-Enabled Sensing for Leak Identification with Oil and Gas Pipeline Maintenance Crews
      with Saurabh Amin and Andrew C. Lee. 2017 International Conference on Unmanned Aircraft Systems, Miami, FL, June 2017.
      ConferenceDOI / Show Abstract

      The U.S. Department of Energy and Transportation considers pipeline security and the timely containment of leaks as a top priority for the oil and natural gas industry. However, despite significant investment in network sensing and maintenance, utilities still incur significant delays (and associated losses) in managing failures. This article focuses on the use of small Unmanned Aerial Systems (sUASs) for the inspection of network components and to facilitate timely repair of failures. Our framework integrates sUAS-enabled sensing with fixed sensing systems and ground-based maintenance crews, and aims to minimize the time to repair multiple network failures. It also reduces human effort in network inspection (e.g. manned reconnaissance, ground patrols, and leak surveys). We consider inspection tasks on a set of failure regions (localization sets) that are generated from fixed sensors installed on the network (e.g. pressure sensors). We focus on the problem of routing a set of available maintenance vehicles at specified yard (base) locations carrying sUASs to optimally identify and repair the network failures. To address this problem, we propose two Mixed-Integer Programming (MIP) formulations: (a) the multi-trip sUAS exploration problem, and (b) maintenance vehicle routing problem. We show that these formulations can be integrated to optimally route the sUASs for identification of multiple network failures that may occur anywhere within the localization sets (MIP-a); and to optimally dispatch maintenance vehicles to repair the identified network failures (MIP-b). We illustrate this approach on a benchmark pipeline network, and demonstrate the inherent tradeoffs between sUAS exploration time and maintenance vehicle travel time in our solution.
    • Network Sensing for Security Against Link Disruption Attacks
      with Saurabh Amin and Lina Sela Perelman. 54th Allerton Conference on Communication, Control and Computing, Urbana, IL, October 2016.
      ConferenceDOI / Show Abstract

      We consider the problem of detecting security failures caused by a resource-constrained attacker using randomized sensing strategies. We propose a game-theoretic model in which the objective of the attacker (resp. defender) is to maximize the number of undetected attacks (resp. detections) on the network. Our game is strategically equivalent to a zero-sum game. Thus, the Nash Equilibria (NE) solution can be found by solving two linear programming (LP) problems. Still, characterization of equilibrium strategies is not tractable for large-scale networks. We assume that the defender’s (resp. attacker’s) detection (resp. attack) budget is limited relative to the size of the network. Under this assumption, we provide structural results on the equilibrium payoffs based on the players’ resources and the size of the minimum set covers. We show that an equilibrium strategy of the defender is to choose a randomized sensing strategy that spans a minimum set cover. This result significantly improves the tractability of NE computation, and provides some practical insights on network sensing in adversarial environments.
    • Network Flow Routing under Strategic Link Disruptions
      with Saurabh Amin. 53rd Allerton Conference on Communication, Control and Computing, Urbana, IL, October 2015.
      ConferenceDOI / Show Abstract

      This paper considers a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender’s expected transportation cost decreases in attacker’s marginal value of lost flow, the attacker’s expected cost of attack increases in defender’s marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.