Green Security Games Along Trails

Abstract

An essential resource in the preservation of earth's biodiversity is keeping large natural areas protected. Unfortunately, sites of ecological interest are constantly threatened by illegal actors and the manpower allocated to monitor and safeguard these spaces is often insufficient. People in charge of taking care of those areas have to optimally allocate the patrolling resources in extensive tracts of land and are often in great disadvantage against the attackers. This problem has been previously studied in the literature and most of the work focuses on open spaces like the African Savannah or requires a discretization of the protected area. These approaches do not capture the reality of South American parks where, due to the density of the vegetation and the ruggedness of the terrain, traveling is done only over a limited collection of available trails (a graph). The problem addressed in this work is the design of near-optimal patrol schedules for rangers in such graphs. We illustrate our results in the trail map of Jamacoaque, a natural reserve in Ecuador. Our central result is that the framework of combinatorial multi-armed bandits is very well suited for this problem and provide theoretical guarantees as well as experimental simulations of our proposed route suggestion algorithms. Additionally, we explore other research directions such as coupling the route suggestion algorithm with additional information provided by an acoustic monitoring system.