In this modern era, every physical asset can be defined by a perimeter and guarding these perimeters is critical from a security and safety perspective. Recent growth in autonomous vehicle technology has led to assigning these monotonous tasks to the autonomous vehicles. This assignment requires design of a set of motion laws for these autonomous vehicles that are both effective and efficient, with provable bounds. This thesis focuses on designing of strategies for a single autonomous vehicle to intercept multiple targets. In this work, we introduce a dynamic vehicle routing problem in which a single vehicle seeks to guard a circular perimeter against radially inward moving targets. The aim of the vehicle is to maximize the capture fraction, i.e., the fraction of targets intercepted before they enter the perimeter. We first obtain a fundamental upper bound on the capture fraction which is independent of any policy followed by the vehicle. We analyze several policies in the low and high arrival rates of target generation. For low arrival, we propose and analyze a First-Come-First-Served and a Look-Ahead policy based on repeated computation of the path that passes through maximum number of unintercepted targets. For high arrival, we design and analyze a policy based on repeated computation of Euclidean Minimum Hamiltonian path through a fraction of existing targets and show that it is within a constant factor of the optimal. Finally, we provide a numerical study of the performance of the policies in parameter regimes beyond the scope of the analysis.
Read
