Persistent Patrol in Stochastic Environments with Limited Sensors
Vu Anh Huynh, John J. Enright, Emilio Frazzoli · 2010
The need for persistent patrol and detection arises in many contexts such as crime prevention, search and rescue, post-conflict stability operations, and peace keeping. In these situations, military or police units are not only effective deterrents to would-be adversaries but also a speedy task force to intercept any trespassers or provide swift security and assistance. With recent advances in technology, unmanned aerial vehicles (UAVs) are well-suited for these tasks because they possess a large bird’s-eye view and are unhindered by ground obstacles. The path planning algorithms used in such missions play a critical role in minimizing the required resources, and maximizing the quality of provided service. Moreover, in many of these mission scenarios, if a patrol pattern is regular or predictable, adversaries can plan a counter strategy to the patrolling effort. In other words, unpredictability is one of the key features of planning in these circumstances. In this work, we propose and analyze the Persistent Patrol and Detection Problem (PPDP), a generic mathematical model for UAVs with limited sensors performing such a mission in a stochastic environment. Incidents occur dynamically and stochastically according to a general renewal process with known time intensity and spatial distribution in a planar region. The UAV is modeled as a point mass traveling at a constant speed with unbounded acceleration. The UAV detects incidents within the footprint of its onboard sensors, i.e., within its visibility range. We want to minimize the expected waiting time between the occurrence of an incident, and its detection epoch. Furthermore, we prefer stochastic trajectories so that would-be adversaries cannot predict the UAV’s motion based on past observations to plan for evasion. Related research focuses on search and rescue missions in which the number of searched objects is known at the beginning of the missions.1,2, 3 In other words, these works present static problems in terms of the number of objects to be found. In contrast, incidents of interest in the PPDP arrive continuously with unknown arrival times, and therefore the search effort must be persistent and preventive. This inherent difference between the PPDP and previous works has made the PPDP a dynamic problem in term of the number of incidents. ∗V. A. Huynh is with the Laboratory of Information and Decision Systems, Massachusetts Institute of Technology, 77 Massachusetts Ave., Cambridge, MA 02139. [email protected] †J. J. Enright is with Kiva Systems, 225 Wildwood Ave, Woburn, MA 01801. [email protected] ‡E. Frazzoli is with the Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts, 02139. [email protected]