Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1408461, author = {Klaška, David and Kučera, Antonín and Lamser, Tomáš and Řehák, Vojtěch}, address = {Richland, SC}, booktitle = {Proceedings of the 2018 International Conference on Autonomous Agents & Multiagent Systems}, doi = {http://dx.doi.org/10.5555/3237383.3237481}, keywords = {patrolling games; single and multi-agent planning and scheduling}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Richland, SC}, isbn = {978-1-5108-6808-3}, pages = {659-666}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, title = {Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games}, url = {http://dl.acm.org/citation.cfm?id=3237383.3237481}, year = {2018} }
TY - JOUR ID - 1408461 AU - Klaška, David - Kučera, Antonín - Lamser, Tomáš - Řehák, Vojtěch PY - 2018 TI - Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games PB - International Foundation for Autonomous Agents and Multiagent Systems CY - Richland, SC SN - 9781510868083 KW - patrolling games KW - single and multi-agent planning and scheduling UR - http://dl.acm.org/citation.cfm?id=3237383.3237481 L2 - http://dl.acm.org/citation.cfm?id=3237383.3237481 N2 - We give a polynomial-time algorithm for synthesizing efficient regular strategies in adversarial patrolling games with general topology. Regular strategies use finite memory to gather some relevant information about the history of Defender's moves which results in substantially better protection of the targets. So far, the scope of automatic strategy synthesis was limited to positional strategies (which ignore the history) or to regular strategies where the underlying finite-memory observer had to be supplied manually. Furthermore, the existing methods do not give any information on how far are the constructed strategies from being optimal. In this paper, we try to overcome these limitations. We develop a novel gradient-based algorithm for synthesizing regular strategies where the underlying finite-memory observers are constructed algorithmically. The running time of our algorithm is polynomial which makes the algorithm applicable to instances of realistic size. Furthermore, we develop an algorithm for computing an upper bound on the best achievable protection, and compare the quality of the constructed strategies against this bound. Thus, we can effectively measure the "distance'' of the constructed strategies from optimal strategies, and our experiments show that this distance is often quite small. ER -
KLAŠKA, David, Antonín KUČERA, Tomáš LAMSER and Vojtěch ŘEHÁK. Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games. Online. In \textit{Proceedings of the 2018 International Conference on Autonomous Agents \&{} Multiagent Systems}. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2018, p.~659-666. ISBN~978-1-5108-6808-3. Available from: https://dx.doi.org/10.5555/3237383.3237481.
|