Multi-Agent Patrolling on a Budget: Finding the Best
Team for the Job
Sara Marie Mc Carthy, Aaron Schlenker, Milind Tambe, and Christopher Kiekintveld
In AAMAS Workshop on Optimization in Multi-Agent Systems (OPTMAS). 2015.
This is the author's version of the work.
Download
Abstract
Research in security games currently focuses on optimizing the use
of defender resources of a given team, with little focus on the problem of which
team to form in the first place. However, in real world domains, we often face the
challenge of selecting a defender team given budget constraints and the requirement
that the team be composed of heterogeneous resources, each with different
costs and utilities. We present three novel contributions to address this challenge
in security games. First we introduce a scalable security game algorithm
for computing defender resource allocations with the ability to model coordination
among resources. This algorithm is used in our second contribution, which
includes heuristic search algorithms to form optimal teams. Finally, we present
detailed experimental results showing that these methods consistently outperform
baseline methods and can scale up to real world problem domains.
