2026-07-23T00:19:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23977 2025-08-18T07:11:51Z ddc:004 open_access

Coverage Games Kupferman, Orna Shenwald, Noam Two-Player Games ω-Regular Objectives Coverage Planning We introduce and study coverage games - a novel framework for multi-agent planning in settings in which a system operates several agents but do not have full control on them, or interacts with an environment that consists of several agents. The game is played between a coverer, who has a set of objectives, and a disruptor. The coverer operates several agents that interact with the adversarial disruptor. The coverer wins if every objective is satisfied by at least one agent. Otherwise, the disruptor wins. Coverage games thus extend traditional two-player games with multiple objectives by allowing a (possibly dynamic) decomposition of the objectives among the different agents. They have many applications, both in settings where the system is the coverer (e.g., multi-robot surveillance, coverage in multi-threaded systems) and settings where it is the disruptor (e.g., prevention of resource exhaustion, ensuring non-congestion). We study the theoretical properties of coverage games, including determinacy, and the ability to a priori decompose the objectives among the agents. We solve the problems of deciding whether the coverer or the disruptor wins, analyze their tight complexity, and consider useful special cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Orna Kupferman and Noam Shenwald 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.27 urn:nbn:de:0030-drops-239776 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode