Resumo Técnico: Coverage Games (Jogos de Cobertura)

1. Introdução e Problema

O artigo introduz e estuda os Jogos de Cobertura (Coverage Games), um novo quadro teórico para o planejamento multiagente em cenários onde o sistema não possui controle total sobre os agentes ou interage com um ambiente composto por vários agentes.

O problema central é modelado como um jogo de dois jogadores:

• O Cobridor (Coverer): Opera um conjunto de $k$ agentes. Seu objetivo é garantir que um conjunto de objetivos $\beta = \{\alpha_1, \dots, \alpha_m\}$ seja totalmente "coberto".
• O Disruptor (Disruptor): Um jogador adversário que interage com todos os agentes do Cobridor simultaneamente, utilizando uma única estratégia. Seu objetivo é impedir que todos os objetivos em $\beta$ sejam satisfeitos.

Condição de Vitória:

• O Cobridor vence se existir uma estratégia (um vetor de estratégias, uma para cada agente) tal que, independentemente da estratégia do Disruptor, cada objetivo $\alpha_l \in \beta$ seja satisfeito por pelo menos um dos $k$ agentes.
• O Disruptor vence se existir uma estratégia tal que, para qualquer estratégia do Cobridor, exista pelo menos um objetivo que não seja satisfeito por nenhum dos agentes.

Diferente dos jogos tradicionais de dois jogadores com objetivos múltiplos (onde um único agente deve satisfazer a conjunção de todos os objetivos), nos Jogos de Cobertura, os objetivos podem ser distribuídos dinamicamente entre os agentes. Se $k=1$, o jogo reduz-se a um jogo padrão com objetivos múltiplos. Se $k \ge m$, o problema é trivial (cada agente assume um objetivo). O caso interessante ocorre quando $1 < k < m$, exigindo uma decomposição dinâmica dos objetivos.

2. Metodologia e Propriedades Teóricas

Os autores analisam a estrutura teórica dos jogos, focando em dois tipos de objetivos clássicos em teoria dos jogos e verificação formal: Büchi (visitar um conjunto de vértices infinitamente muitas vezes) e co-Büchi (evitar um conjunto de vértices infinitamente muitas vezes).

2.1. Indeterminação

Um dos resultados teóricos fundamentais é que os Jogos de Cobertura não são determinados. Diferente dos jogos de dois jogadores padrão (onde sempre existe um vencedor com uma estratégia vencedora), em um Jogo de Cobertura, pode ocorrer que nem o Cobridor nem o Disruptor possuam uma estratégia vencedora. Isso decorre da informação incompleta dos agentes do Cobridor sobre os outros agentes e da incapacidade do Disruptor de explorar essa informação de forma coordenada entre os agentes.

2.2. Decomposibilidade de Objetivos

O artigo define o conceito de decomposibilidade a priori.

• Um conjunto de objetivos $\beta$ é decomponível em $l$ subconjuntos se o Cobridor puder atribuir permanentemente $l$ subconjuntos de objetivos a subconjuntos específicos de agentes.
• O trabalho demonstra que, em geral, não é possível decompor os objetivos a priori. O Cobridor frequentemente precisa reagir dinamicamente às escolhas do Disruptor, dividindo os objetivos apenas quando o jogo atinge certos "pontos de bifurcação" (forks) no grafo do jogo.
• A caracterização de estratégias vencedoras baseia-se na identificação desses forks e na redução do problema a subproblemas menores ou a jogos de um único jogador em subgrafos onde o Disruptor não pode evitar os forks.

3. Resultados de Complexidade Computacional

Os autores realizam uma análise abrangente da complexidade dos problemas de Cobertura (decidir se o Cobridor vence) e Disrupção (decidir se o Disruptor vence), considerando o tamanho do grafo do jogo ($G$), o número de objetivos ($|\beta|$) e o número de agentes ($k$).

3.1. Complexidade Conjunta (Geral)

• Problema de Cobertura: É PSPACE-completo para objetivos Büchi e co-Büchi. Isso é significativamente mais difícil do que jogos de dois jogadores com objetivos múltiplos (que são em PTIME para certas classes), devido à necessidade de explorar recursivamente as decomposições de objetivos.
• Problema de Disrupção: É $\Sigma_2^P$-completo (segundo nível da hierarquia polinomial). Embora o jogo não seja determinado, o problema de verificar se o Disruptor vence é computacionalmente mais "fácil" (na hierarquia de complexidade) do que o problema de Cobertura.

3.2. Complexidade Parametrizada

Os autores analisam cenários onde parâmetros específicos são fixos, o que é comum em aplicações práticas onde o grafo é grande, mas o número de agentes ou objetivos é pequeno.

Cenário	Complexidade (Cobertura)	Complexidade (Disrupção)	Observações
$k$ fixo (número de agentes)	NP-completo	NP-completo (Büchi) $\Sigma_2^P$-completo (co-Büchi)	Para co-Büchi, a complexidade permanece alta mesmo com poucos agentes devido à dificuldade de encontrar conjuntos máximos de objetivos satisfatórios.
$|\beta|$ fixo (número de objetivos)	PTIME	PTIME	Fixar o número de objetivos elimina a nondeterminismo na decomposição, tornando o problema tratável em tempo polinomial.
$k \ge |\beta|$	PTIME	PTIME	Reduz-se a $|\beta|$ jogos de dois jogadores independentes.
Um jogador (V = V1 ou V2)	NP-completo (Büchi) NLOGSPACE (co-Büchi, $k$ fixo)	NLOGSPACE	No caso de um jogador, o problema de Cobertura com Büchi é NP-completo (relacionado ao problema de cobertura de caminhos).

Diferença Crucial entre Büchi e co-Büchi:
Enquanto para o problema de Cobertura as complexidades de Büchi e co-Büchi coincidem na maioria dos casos, para o problema de Disrupção com $k$ fixo, há uma divergência:

• Büchi: Disrupção é NP.
• co-Büchi: Disrupção é $\Sigma_2^P$.
  Isso ocorre porque, no caso co-Büchi, a dificuldade de encontrar conjuntos máximos de objetivos que um agente pode satisfazer sozinho (em um jogo de um jogador) já é NP-difícil, elevando a complexidade do problema de disrupção.

4. Contribuições Principais

1. Definição Formal: Estabelecimento dos Jogos de Cobertura como um modelo para planejamento multiagente com controle parcial e objetivos compartilhados.
2. Teoria da Indeterminação: Prova de que esses jogos não são determinados, introduzindo a necessidade de analisar estratégias de cobertura e disrupção separadamente.
3. Caracterização de Estratégias: Desenvolvimento de uma caracterização baseada em forks (pontos de decisão) e decomposição dinâmica de objetivos, que serve como base para os algoritmos de decisão.
4. Análise de Complexidade Completa: Mapeamento preciso das classes de complexidade (PSPACE, $\Sigma_2^P$, NP, PTIME) para diferentes variações do problema, destacando a assimetria entre os problemas de Cobertura e Disrupção e entre objetivos Büchi e co-Büchi.
5. Reduções e Algoritmos: Construção de reduções de problemas como QBF (Quantified Boolean Formulas) e 3SAT para provar limites inferiores, e desenvolvimento de algoritmos recursivos e simbólicos para limites superiores.

5. Significado e Aplicações

O trabalho tem implicações significativas para várias áreas da ciência da computação e engenharia de sistemas:

• Robótica Multiagente: Permite modelar cenários de patrulha e vigilância onde um conjunto de robôs deve cobrir múltiplas áreas críticas, mesmo na presença de um ambiente adversário ou dinâmico.
• Cibersegurança: Modela sistemas de defesa onde múltiplos mecanismos de defesa devem mitigar diferentes vetores de ataque, contra um hacker adversário.
• Sistemas Multithreaded: Aplica-se à garantia de que recursos críticos sejam acessados infinitamente muitas vezes por pelo menos um processo, em ambientes onde o escalonador (ou o ambiente) é adversário.
• Teste de Software: Relaciona-se à cobertura de funcionalidades de software em todas as sequências de entrada possíveis.

A principal contribuição teórica é mostrar que a introdução de múltiplos agentes com objetivos compartilhados, mas sem controle total, transforma problemas que seriam tratáveis (PTIME) em problemas de alta complexidade (PSPACE ou $\Sigma_2^P$), exigindo novas abordagens algorítmicas que lidem com a decomposição dinâmica de tarefas.