Resumo Técnico: Alocação Preditiva com Gatilho de Confiança (TGPR)

Declaração do Problema

A alocação de tarefas multi-robô (MRTA) descentralizada normalmente depende de leilões baseados em mercado (ex: Protocolo de Rede de Contrato, CBBA) que assumem a entrega confiável de mensagens. Em implantações no mundo real, a comunicação sem fio é instável devido à perda de percurso, interferência e, criticamente, à degradação persistente de hardware (ex: antenas gastas, transmissores limitados por potência) que varia de robô para robô.

Os métodos robustos atuais abordam isso ou reduzindo a frequência das mensagens ou reatribuindo tarefas apenas após a detecção de uma falha. Essas abordagens tratam a incerteza de comunicação como um incômodo de agendamento a ser absorvido por tentativas de reenvio ou reconciliação periódica, em vez de uma quantidade aprendível. Além disso, os modelos de "confiança" existentes em MRTA focam na capacidade de um agente completar uma tarefa, não na confiabilidade do link de comunicação em si. Isso leva a dois modos primários de falha em redes com perda de pacotes:

1. Inanição (Starvation): Uma tarefa é concedida, mas o reconhecimento (acknowledgment) é perdido; o coordenador espera indefinidamente enquanto nenhum outro robô intervém.
2. Duplicação: O coordenador aguarda um tempo limite (timeout) esperando por um reconhecimento atrasado (mas não perdido) e reatribui a tarefa, fazendo com que dois robôs executem a mesma tarefa.

Metodologia: Alocação Preditiva com Gatilho de Confiança (TGPR)

O TGPR é um mecanismo de leilão descentralizado que integra uma estimativa bayesiana por robô da confiabilidade da ida e volta da comunicação em um ciclo padrão de anúncio-lance-concessão-reconhecimento. Ele modifica a lógica de decisão do coordenador sem alterar o protocolo de mensagem subjacente.

1. Estimativa de Confiança Bayesiana de Ida e Volta (Round-Trip)

O coordenador mantém uma distribuição posterior Beta, $Beta(\alpha_i, \beta_i)$, para cada robô $i$, representando a probabilidade de um ciclo bem-sucedido de concessão-reconhecimento.

• Atualizações: Os parâmetros são atualizados com base nos resultados observados (sucesso no atraso $\delta$ ou tempo esgotado).
• Decaimento: Um fator de decaimento $\lambda < 1$ permite que a estimativa acompanhe condições não estacionárias (ex: falhas de hardware desenvolvendo-se no meio da missão).
• Pontuação de Confiança: A confiabilidade estimada é $\hat{p}_i = \alpha_i / (\alpha_i + \beta_i)$.

2. Avaliação de Lance com Desconto de Confiança

Ao contrário dos leilões padrão que classificam os licitantes pelo utilidade bruta ($u_{ij}$), o TGPR classifica os candidatos por uma utilidade com desconto de confiança:
$$\hat{u}_{ij} = u_{ij} \cdot \hat{p}_i$$
Isso prioriza robôs que são capazes e alcançáveis, distinguindo entre um robô altamente capaz com um link historicamente ruim e um robô ligeiramente menos capaz com um link confiável.

3. Tempo Limite Preditivo Adaptativo

Em vez de um tempo limite global fixo, o TGPR calcula um tempo limite por robô $\tau_i$ baseado na distribuição de atraso aprendida:
$$\tau_i = \text{clip}(\mu_i + z\sigma_i, \tau_{min}, \tau_{max})$$
Isso concede paciência a links historicamente lentos, mas confiáveis, enquanto permite uma recuperação rápida para links que nunca falharam.

4. Reivindicação Unilateral de Espectador Baseada em Confiança

Para reduzir a latência de recuperação, robôs ociosos que ouvem um anúncio de concessão podem reivindicar uma tarefa se o prazo anunciado expirar sem uma transmissão de confirmação.

• Mecanismo: Se um espectador reivindicar a tarefa, o coordenador tenta cancelar o detentor original.
• Janela de Graça: Uma curta janela de graça evita que a reivindicação do espectador corra contra a própria lógica de fallback do coordenador, garantindo que a lógica de reatribuição do coordenador não seja preempida prematuramente.

Principais Contribuições

1. Design de Testbed: Um simulador de eventos discretos com um modelo de canal apresentando perda dependente de distância, jamming transiente e um fator de confiabilidade de hardware persistente e aprendível por robô ($h_i$). Os autores demonstram que, sem esse diferencial persistente, mecanismos baseados em confiança não oferecem vantagem sobre heurísticas baseadas em distância.
2. Algoritmo TGPR: Um novo mecanismo de leilão combinando lances com desconto de confiança, tempos limite adaptativos por robô e reivindicação de espectador.
3. Avaliação Controlada: Uma comparação sistemática contra três baselines (Timeout fixo ingênuo, Backoff exponencial e Reconciliação periódica) através de cinco regimes de qualidade de canal, dois tamanhos de equipe e uma ablação de heterogeneidade de hardware.

Resultados Experimentais

O estudo avaliou 4.800 ensaios de varredura principal e 2.000 ensaios de ablação.

Eficiência e Redução de Desperdício

O TGPR demonstra melhorias estatisticamente significativas na eficiência de comunicação e na redução de desperdício:

• Execução Duplicada: Reduzida em 23,9% em relação ao baseline ingênuo (10,65% vs. 13,99%).
• Sobrecarga de Mensagens: Reduzida em 13,6% (167,2 vs. 193,6 mensagens por tarefa concluída).
• Tendência: Essas vantagens crescem conforme a qualidade do canal piora e conforme a fração de robôs com hardware degradado aumenta.

Taxa de Conclusão de Tarefas

Ao contrário da hipótese de que a alocação consciente da confiabilidade melhoraria o throughput geral, o TGPR não melhora a taxa de conclusão de tarefas.

• Desempenho: Em condições de canal ruins e severos, o TGPR conclui significativamente menos tarefas do que o baseline de timeout fixo ingênuo (ex: 0,434 vs. 0,466 em condições severas com $N=25$).
• Achado de Ablação: A lacuna na taxa de conclusão aumenta (de 1,1% para 1,9%) conforme a fração de hardware degradado aumenta, contradizendo a expectativa de que o mecanismo de confiança "compensaria" seu custo evitando hardware ruim.

Causa Raiz do Custo de Conclusão de Tarefas

Os autores atribuem o déficit na taxa de conclusão a dois mecanismos específicos:

1. Inflação de Variância Não Limitada: Sob altas taxas de falha sustentadas, a regra de atualização do timeout adaptativo infla a estimativa de variância de atraso ($\sigma_i$) sem decaimento suficiente. Isso faz com que os timeouts aprendidos aumentem progressivamente em direção ao limite máximo, perdendo o poder discriminativo entre robôs saudáveis e degradados.
2. Taxa de Latência Fixa: A janela de graça da reivindicação do espectador introduz um atraso fixo em cada ciclo de recuperação, acumulando custo sob falhas frequentes.

A análise de sensibilidade de parâmetros confirma que reduzir o multiplicador de timeout ($z$) pode recuperar a taxa de conclusão ao custo de aumentar duplicatas e mensagens, indicando um trade-off controlável em vez de uma falha fundamental na estimativa de confiança.

Significância e Alegações

O artigo posiciona o TGPR não como uma melhoria universal para leilões mais simples, mas como uma solução especializada para restrições operacionais específicas.

• Fronteira Operacional: O TGPR é uma vitória substancial para implantações onde a largura de banda de comunicação é escassa ou o esforço físico duplicado (ex: consumo de bateria, desgaste em atuadores) é a restrição limitante. Nesses cenários, a redução no desperdício e na sobrecarga de mensagens é a métrica principal de sucesso.
• Limitação: Quando a única métrica é o throughput bruto de conclusão de tarefas em ambientes hostis, o TGPR não é uma melhoria estrita em relação aos baselines de timeout fixo mais simples e pode ter desempenho inferior.
• Insight Científico: O estudo fornece um contraexemplo crítico à suposição de que a "confiança" sempre ajuda. Demonstra que mecanismos baseados em confiança requerem um sinal persistente e aprendível (degradação de hardware) para serem eficazes; em frotas onde a não confiabilidade é puramente posicional e transitória, mecanismos de confiança não oferecem benefício mensurável.
• Relato Honesto: Os autores relatam explicitamente o trade-off, observando que o custo do mecanismo (redução na taxa de conclusão) cresce com a heterogeneidade do hardware, contrariando as expectativas iniciais, e atribuem isso a comportamentos algorítmicos específicos (inflação de variância) em vez de fatores externos.

O trabalho conclui que o TGPR oferece um trade-off valioso e quantificável: sacrificar parte do throughput de conclusão de tarefas para reduzir significativamente a sobrecarga de comunicação e a execução duplicada, desde que o ambiente de implantação exiba diferenciais de confiabilidade de hardware persistentes e aprendíveis.