ONLINE PURSUIT ALGORITHMS AND OPTIMAL STRATEGIES FOR HETEROGENEOUS ROBOTS

The advancement in technology, especially Unmanned Aerial Vehicles (UAVs) or drones, has helped mankind in many aspects of everyday life, such as environmental monitoring and in surveillance. However, an easy access to UAV technology has spurred its malicious use, leading to numerous attempts of flying UAVs into restricted areas or in public places. One possible way to counter against such adversarially intruding UAVs is to tag or disable them before they reach a specified location by using superior drones. But the problem of how to plan the motion of these drones, i.e., designing algorithms that have provable guarantees on the numbers of adversarial UAVs that can be disabled has remained an open problem. This dissertation addresses design of control strategies and online algorithms, i.e., algorithms that do not have information about the intruders a priori, for drones to pursue and disable one or many intruders and is divided into two parts. The first part involves many, possibly infinite, intruders that move directly towards a region of interest. For this scenario, we design decentralized as well as cooperative online algorithms with provable worst-case guarantees for 1) a single drone defender, 2) a team of homogeneous defenders, and 3) a team of heterogeneous defenders. The aim of such defender drones is to capture as many intruders as possible that arrive in the environment. To quantify how well the algorithms perform in the worst-case, we adopt a competitive analysis technique. In particular, the algorithms designed in this dissertation exhibit a finite competitive ratio, meaning that the performance of an online algorithm is no worse than a finite value determined in this dissertation. We also determine fundamental limits on the existence of online algorithms with finite competitive ratios.In terms of heterogeneity, the first part addresses drones of different capabilities as well as motion models, such as a drone and a turret operating in the same environment. The second part of this dissertation considers coupling between the motion. Specifically, this part considers a laser attached to a fixed wing aircraft. The aircraft is modelled as a planar Dubins vehicle and the laser with a finite range can rotate clockwise or anti-clockwise. We design an optimal control strategy for both the Dubins vehicle and the laser such that a static target, located in the environment, is tagged in minimum time. By applying the minimum principle, we establish cooperative properties between the laser and the Dubins vehicle. We further establish that the shortest path must lie in a family of 13 candidate paths and characterize the solutions to all of these types. Finally, this part also addresses a scenario when the location of the perimeter is not precisely known to the adversary requiring the adversary to release surveilling agents to estimate the location of the perimeter. Specifically, a pursuit problem of surveilling agents is considered wherein the objective of the pursuer is to capture any one of the surveilling agents whereas the surveilling agents aim to jointly maximize a weighted combination of the determinant of the Fisher Information Matrix and the distance to the pursuer from the nearest tracker. We establish the optimal strategy for the pursuer and show that the optimization problem for the surveilling agents can be converted to a Quadratically Constrained Quadratic Program. We further establish that the optimal strategies obtained for the pursuer and the trackers form a Nash equilibrium of this game.