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 acompetitive analysisapproach 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 ofanyalgorithm. 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.

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.

We model a finite horizon decision making process between an ego and a non-ego vehicle, where the non-ego vehicle has a certain probability of moving adversarially over each planning stage. The adversarial intent of the non-ego vehicle is inferred only when a particular set of actions are performed by both vehicles, thereby creating a stopping state. We term such a decision-making process as a multi-stage stochastic zero-sum game (SSG) with stopping states, i.e., once adversarial intent is ascertained, the non-ego vehicle continues to choose its actions adversarially for the remaining stages of the interaction. We analytically characterize the Nash equilibria of this game for the case of two actions per player. We then demonstrate this approach via two autonomous motion planning applications. The first involves maintaining a safe distance from a non-ego vehicle ahead, modeled using fixed stage costs. The second involves safe lane-changing with costs that are stage dependent. In both scenarios, we provide a comparison between the analytic/simulated and experimental results using ground robots.

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 underfull 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 apartial 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.

This paper studies a motion planning problem over a roadmap in which a vehicle aims to travel from a start to a destination in presence of an attacker who can launch a cyber-attack on the vehicle over any one edge of the roadmap. The vehicle (defender) has the capability to switch on/off a countermeasure that can detect and permanently disable the attack if it occurs concurrently. We first model the problem of traversing an edge as a zero-sum dynamic game with a stopping state, termed as an edge-game played between an attacker and defender. We characterize Nash equilibria of the edge-game and provide closed form expressions for the case of two actions per player. We further provide an analytic and approximate expression on the value of an edge-game and characterize conditions under which it grows sub-linearly with the length of the edge. We study the sensitivity of Nash equilibrium to the (i) cost of using the countermeasure, (ii) cost of motion and (iii) benefit of disabling the attack. The solution of the edge-game is used to formulate and solve the secure route planning problem. We design an efficient heuristic by converting the problem to a shortest path problem using the edge cost as the solution of corresponding edge-games. We illustrate our findings through several insightful simulations.

Achieving and maintaining line-of-sight (LOS) is challenging for underwater optical communication systems, especially when the underlying platforms are mobile. In this work, we propose and demonstrate an active alignment controlbased LED-communication system that uses the DC value of the communication signal as feedback for LOS maintenance. Utilizing the uni-modal nature of the dependence of the light signal strength on local angles, we propose a novel triangular exploration algorithm, that does not require the knowledge of the underlying light intensity model, to maximize the signal strength that leads to achieving and maintaining LOS. The method maintains an equilateral triangle shape in the angle space for any three consecutive exploration points, while ensuring the consistency of exploration direction with the local gradient of signal strength. The effectiveness of the approach is first evaluated in simulation by comparison with extremum-seeking control, where the proposed approach shows a significant advantage in the convergence speed. The efficacy is further demonstrated experimentally, where an underwater robot is controlled by a joystick via LED communication.

Adversary emulation is an offensive exercise that provides a comprehensive assessment of a system's resilience against cyber attacks. However, adversary emulation is typically a manual process, making it costly and hard to deploy in cyber-physical systems (CPS) with complex dynamics, vulnerabilities, and operational uncertainties. In this paper, we develop an automated, domain-aware approach to adversary emulation for CPS. We formulate a Markov Decision Process (MDP) model to determine an optimal attack sequence over a hybrid attack graph with cyber (discrete) and physical (continuous) components and related physical dynamics. We apply model-based and model-free reinforcement learning (RL) methods to solve the discrete-continuous MDP in a tractable fashion. As a baseline, we also develop a greedy attack algorithm and compare it with the RL procedures. We summarize our findings through a numerical study on sensor deception attacks in buildings to compare the performance and solution quality of the proposed algorithms.

Kernel methods for machine learning have a strong mathematical basis and a proven modeling power. However, scalability of these methods is limited by the intensive computations they require. More specifically, for Gaussian Process, the covariance matrix needs to be inverted to compute the posterior distribution and to optimize the hyperparameters of the employed kernel. Scalability requirement of the matrix inversion computations grows with the number of points in the training data, which hinders applicability of the method to streaming and big data analytics applications. In this paper, we briefly review our recent sequential Gaussian process approach. Then, we propose an incremental hyperparameter optimization algorithm for polynomial kernels.

The Gaussian process framework models a function as a stochastic process such that the training data results into a finite number of jointly Gaussian random variables, whose properties can then be used to infer the statistics (the mean and variance) of the function at test values for the input. The computation can be implemented in a batch setting, i.e., one-shot over the entire training data, or in a sequential setting where the data is processed incrementally. In either setting, the scalability of the computation grows with the number of points in the (training) data. This paper addresses the scalability aspect of Gaussian processes in sequential settings using recent advances in randomized matrix computations.

We consider the task of actively exploring unstructured environments to facilitate robotic grasping of occluded objects. Typically, the geometry and locations of these objects are not known a priori. We mount an RGB-D sensor on the robot gripper to maintain a 3D voxel map of the environment during exploration. The objective is to plan the motion of the sensor in order to search for feasible grasp handles that lie within occluded regions of the map. In contrast to prior work that generates exploration trajectories by sampling, we directly optimize the exploration trajectory to find grasp handles. Since it is challenging to optimize over the discrete voxel map, we encode the uncertainty of the positions of the occluded grasp handles as a mixture of Gaussians, one per occluded region. Our trajectory optimization approach encourages exploration by penalizing a measure of the uncertainty. We then plan a collision-free trajectory for the robot arm to the detected grasp handle. We evaluated our approach by actively exploring and attempting 300 grasps. Our experiments suggest that compared to the baseline method of sampling 10 trajectories, which successfully grasped 58% of the objects, our active exploration formulation with trajectory optimization successfully grasped 93% of the objects, was 1.3× faster, and had 3.2× fewer failed grasp attempts.

We present a novel path planning algorithm that, starting from a probabilistic roadmap, efficiently constructs a product graph used to search for a near optimal solution of a multiobjective optimization problem. The goal is to find paths that minimize a primary cost, such as the path length from start to goal, subject to a bound on a secondary cost such as the state estimation error covariance. The proposed algorithm is efficient as it relies on a scalar metric, related to the largest eigenvalue of the error covariance, and adaptively quantizes the secondary cost, yielding a product graph whose number of vertices and edges provides a good tradeoff between optimality and computational complexity. We further show how our approach can be extended to handle constraints on the probability of collision avoidance specified at every vertex along the path. Numerical examples show 1) how the computed paths change as a function of the specified bound on the secondary costs, and 2) the tradeoff between accuracy and computational efficiency of the proposed approach compared with methods where the product graph is built by quantizing the secondary cost uniformly.

This paper considers the problem of planning a path for an autonomous vehicle from a start to a goal location in presence of sensor intermittency modeled as a stochastic process, in addition to process and measurement noise. The aim is to plan a path that minimizes the localizational uncertainty for the vehicle upon arriving at the goal location. The main contribution of this paper is two-fold. We first show that it is possible to obtain an analytical bound on the performance of a state estimator under sensor misdetection (intermittency) occurring stochastically over time. We then use this bound in a sample-based path planning algorithm to produce a path that trades off accuracy and robustness. This extends the recent body of work on planning under uncertainty to include the fact that sensors may not provide any measurement owing to misdetection. This is caused either by adverse environmental conditions that prevent the sensors from making measurements or by the fundamental limitations of the sensors. Examples include RF-based ranging devices that intermittently do not receive the signal from beacons because of obstacles or the misdetection of features by a camera system in detrimental lighting conditions. Computational results demonstrate the benefit of the approach and comparisons are made with the state of the art in path planning in belief space.

We consider the problem of dynamic vehicle routing under exact-time constraints on servicing demands. Demands are sequentially generated in an environment, and every demand needs to be serviced exactly after a fixed finite interval of time after it is generated. We design routing policies for a service vehicle to maximize the fraction of demands serviced at steady state. The main contributions are as follows. First, we demonstrate that this problem is described by an appropriate directed acyclic graph structure which leads to a computationally efficient routing algorithm based on a longest-path computation. Second, under the assumption of the demands being generated uniformly randomly in the environment and via a Poisson process in time, we provide two analytic lower bounds on the service fraction of the longest path policy. The first bound is relative to an optimal noncausal version of the policy, i.e., a policy based on knowledge of all future demand requests. The second bound is an explicit function of the vehicle dynamics and demand generation rate and, therefore, useful as a design tool. Finally, we present numerical results to support the analytic bounds.

In this paper, we address discrete-time pursuit-evasion games in the plane where every player has identical sensing and motion ranges restricted to closed disks of given sensing and stepping radii. A single evader is initially located inside a bounded subset of the environment and does not move until detected. We propose asweep-pursuit-capturepursuer strategy to capture the evader and apply it to two variants of the game. The first involves a single pursuer and an evader in a bounded convex environment, and the second involves multiple pursuers and an evader in a boundaryless environment. In the first game, we give a sufficient condition on the ratio of sensing to stepping radius of the players that guarantees capture. In the second, we determine the minimum probability of capture, which is a function of a novel pursuer formation and independent of the initial evader location. The sweep and pursuit phases reduce both games to previously studied problems with unlimited range sensing, and capture is achieved using available strategies. We obtain novel upper bounds on the capture time and present simulation studies that address the performance of the strategies under sensing errors, different ratios of sensing to stepping radius, greater evader speed, and a different number of pursuers.