Dual-Mandate Patrols: Multi-Armed Bandits for Green Security
Dual-Mandate Patrols: Multi-Armed Bandits for Green Security
复制标题
DOI：
10.1609/aaai.v35i17.17757
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Lily Xu;Elizabeth Bondi-Kelly;Fei Fang;A. Perrault;Kai Wang;Milind Tambe
中科院分区：
文献类型：
--
作者：
Lily Xu;Elizabeth Bondi-Kelly;Fei Fang;A. Perrault;Kai Wang;Milind Tambe
在绿色安全领域保护野生动物和森林的努力受到防御者（即巡逻者）有限可用性的限制，他们必须在广阔的地区巡逻以保护免受攻击者（如偷猎者或非法伐木者）的攻击。防御者必须选择在保护区的每个区域花费多少时间，平衡探索不常访问的区域和利用已知热点。我们将问题表述为一个随机的多武装强盗，其中每个行动代表一个巡逻策略，使我们能够保证巡逻策略的收敛速度。然而，一个天真的强盗方法会为了长期的最优而牺牲短期的表现，导致动物被偷猎和森林被破坏。为了提高性能，我们利用了奖励函数的平滑性和动作的可分解性。我们展示了李普希茨连续性和分解之间的协同作用，因为每一个都有助于另一个的收敛。在此过程中，我们弥合了组合和Lipschitz强盗之间的差距，提出了一种无悔的方法，在优化短期性能的同时收紧了现有的保证。我们证明了我们的算法，蜥蜴，提高了来自柬埔寨的真实偷猎数据的性能。
Conservation efforts in green security domains to protect wildlife and forests are constrained by the limited availability of defenders (i.e., patrollers), who must patrol vast areas to protect from attackers (e.g., poachers or illegal loggers). Defenders must choose how much time to spend in each region of the protected area, balancing exploration of infrequently visited regions and exploitation of known hotspots. We formulate the problem as a stochastic multi-armed bandit, where each action represents a patrol strategy, enabling us to guarantee the rate of convergence of the patrolling policy. However, a naive bandit approach would compromise short-term performance for long-term optimality, resulting in animals poached and forests destroyed. To speed up performance, we leverage smoothness in the reward function and decomposability of actions. We show a synergy between Lipschitz-continuity and decomposition as each aids the convergence of the other. In doing so, we bridge the gap between combinatorial and Lipschitz bandits, presenting a no-regret approach that tightens existing guarantees while optimizing for short-term performance. We demonstrate that our algorithm, LIZARD, improves performance on real-world poaching data from Cambodia.