Secure Route Planning Using Dynamic Games with Stopping States

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.