PhD Proposal: Robot planning in adversarial environments using tree search techniques

One of the main advantages of robots is that they can be used in environments that are dangerous for humans. Robots can be used not only for tasks in known and safe areas but also in environments that may have adversaries. Scenarios include reconnaissance in contested environments, adversarial target tracking (pursuit-evasion), and robotics competition games. When planning the robot’s actions in such scenarios, we have to consider the outcomes of not only the robot’s actions but also the actions taken by the adversary as well as the information available to the adversary.This thesis aims to design planning strategies that improve the robot's performance in adversarial environments. Specifically, we study how the availability of information affects the planning process and the outcome. We also study how to improve computational efficiency exploiting the structural properties of the underlying setting.We adopt a game-theoretic formulation and study two scenarios: adversarial, active target tracking and reconnaissance in environments with adversaries. A conservative approach is plan robot’s action assuming a worst-case adversary that has complete knowledge of the robot’s state and objective function and of the environment. We start with such a “symmetric” information game for the adversarial target tracking scenario with noisy sensing. By using properties of Kalman filters, we design a pruning strategy to improve the efficiency of a tree search algorithm. We then investigate the performance limits of asymmetric version where the adversary can inject false sensing data of the robot. We then study the reconnaissance scenario considering the robot and the adversary have symmetric information. This method offers guarantees on the success, defined, for example, by scouting more area while avoiding being detected. On the other hand, the symmetric adversarial model may yield plans that are too conservative when the adversary may not have the same information as the robot. Furthermore, the information available to the adversary may change during execution. We have investigated the static version of this “asymmetric” information game, and show how much the robot can exploit the asymmetry in information using tree search techniques. We propose to build on this and further study scenarios where the information available to the adversary changes during execution. We will devise new algorithms for this asymmetric information game with theoretical performance guarantees and evaluate those approaches through realistic simulations.Examining Committee:

Chair: Dr. Pratap Tokekar Dept rep: Dr. Huaishu Peng Members: Dr. Dinesh Manocha Dr. Edmund H. Durfee