30 September 2019 in Journal of Mechanical Design
9 January 2024 in IEEE Transactions on Robotics
In this article, we consider a perimeter defense problem in a planar conical environment in which $M$ identical vehicles, each having a finite capture radius, seek to defend a concentric perimeter from mobile intruders. The intruders are released at the circumference of the environment at arbitrary times and in any number. Upon release, each intruder moves radially toward the perimeter with fixed speed. We provide a worst-case analysis of this problem. Specifically, we present a competitive analysis approach to this problem by measuring the performance of decentralized and cooperative online algorithms for the vehicles against arbitrary inputs, relative to an optimal offline algorithm that has information about entire intruder release sequence in advance. We first establish a necessary condition on the problem parameters that guarantees finite competitiveness of any algorithm. We then design and analyze three decentralized and two cooperative online algorithms and characterize parameter regimes in which they have finite competitive ratios. Specifically, our first two decentralized algorithms are provably 1 and 2-competitive, respectively, whereas our third decentralized algorithm exhibits different competitive ratios in different regimes of problem parameters. Our first cooperative algorithm is 1.5-competitive and our second cooperative algorithm exhibits different competitive ratios in different regimes of problem parameters. Finally, we provide multiple numerical plots in the parameter space to reveal additional insights into the relative performance of our algorithms and discuss an extension to the case of heterogeneous vehicles.
12 July 2019 in IEEE Robotics and Automation Letters
Given a nonlinear dynamical system, this letter considers the problem of selecting a subset of the total set of sensors that has provable guarantees on standard metrics related to the nonlinear observability Gramian. The key contribution is a simple randomized algorithm that samples the sensors uniformly without replacement, and yields probabilistic guarantees on the minimum eigenvalue or the inverse of the condition number of the nonlinear observability Gramian relative to that of the complete set of sensors. Numerical studies reveal that the utility of the theoretical results lies in the regime of large total number of sensors wherein the combinatorial nature of the problem presents a significant computational challenge. The results are demonstrated numerically on a problem of moving target localization using an extended Kalman filter in two scenarios: one using range sensors and another with time-difference-of-arrival measurements. A graceful degradation of performance with a decreased number of sensors is observed when compared to the use of all of the sensors for localization. It is also observed that for certain metrics, the proposed approach provides an improvement over a heuristic that selects the sensors in a greedy manner based on the contribution of an additional sensor toward the observability Gramian metric.
13 July 2023 in ACM Transactions on Cyber-Physical Systems
Security of cyber-physical systems (CPS) continues to pose new challenges due to the tight integration and operational complexity of the cyber and physical components. To address these challenges, this article presents a domain-aware, optimization-based approach to determine an effective defense strategy for CPS in an automated fashion—by emulating a strategic adversary in the loop that exploits system vulnerabilities, interconnection of the CPS, and the dynamics of the physical components. Our approach builds on an adversarial decision-making model based on a Markov Decision Process (MDP) that determines the optimal cyber (discrete) and physical (continuous) attack actions over a CPS attack graph. The defense planning problem is modeled as a non-zero-sum game between the adversary and defender. We use a model-free reinforcement learning method to solve the adversary’s problem as a function of the defense strategy. We then employ Bayesian optimization (BO) to find an approximate best-response for the defender to harden the network against the resulting adversary policy. This process is iterated multiple times to improve the strategy for both players. We demonstrate the effectiveness of our approach on a ransomware-inspired graph with a smart building system as the physical process. Numerical studies show that our method converges to a Nash equilibrium for various defender-specific costs of network hardening.
24 November 2021 in IEEE Transactions on Robotics
In this article, we consider a path planning problem on a graph, wherein a vehicle (defender) seeks to find an optimal path from a source to a destination vertex in the presence of an attacker. The defender is equipped with a countermeasure that can detect and permanently disable the attack if it occurs concurrently. We model the problem over an edge as a zero-sum multistage game played between the defender and the attacker with a stopping state, termed as the edge game. We analyze this game under full information , in which each player has complete knowledge of the past actions taken by the opponent at every stage. We also analyze the game under a partial information structure , wherein the defender obtains complete knowledge of the attacker’s actions only when the defender uses the countermeasure. We characterize the Nash equilibria of the edge game in both information structures with two actions per player and analyze its sensitivity to the game parameters. We then construct a meta-game using the edge game solutions to determine an attack-resilient path and compare it with an efficient novel heuristic with a constraint on the number of edges attacked. We illustrate our methodology through simulations in a Robot Operating System/Gazebo environment and with experiments on a ground robot.