Resumo Técnico: Alocação de Tarefas Agêntica para Sistemas Multirrobôs Heterogêneos

1. Formulação do Problema

O artigo aborda o problema de Alocação de Tarefas Multirrobôs (MRTA) em equipes heterogêneas, especificamente a variante de Tarefa Única–Robô Múltiplo (MT–SR). O objetivo é atribuir um conjunto de tarefas $T$ a um conjunto de robôs heterogêneos $R$ sob restrições espaciais, temporais e operacionais.

O problema é formulado como um problema de otimização combinatória binária visando minimizar o makespan (o tempo máximo de conclusão entre todos os robôs). O modelo de custo considera:

• Tempo de Execução: Determinado pela duração nominal da tarefa e por um fator de capacidade específico do robô (coeficiente de habilidade).
• Tempo de Deslocamento: Determinado pela distância entre a posição atual do robô e a localização da tarefa, dividida pela velocidade de cruzeiro do robô.

Os autores identificam que as abordagens tradicionais, como Programação Inteira Mista (MIP) e buscas heurísticas, têm dificuldade em equilibrar escalabilidade computacional com qualidade de solução, particularmente ao lidar com intenções humanas de alto nível, domínios dinâmicos e especificações de tarefas ambíguas. Além disso, os métodos tradicionais frequentemente sofrem com ótimos locais e problemas de escala em grafos de tarefas grandes e dinâmicos.

2. Metodologia: Uma Abordagem Híbrida de LLM e Busca Local

A solução proposta é uma estrutura de otimização híbrida que integra um Modelo de Linguagem de Grande Escala (LLM) como um motor de raciocínio cognitivo com um algoritmo de busca local livre de derivadas chamado Speed-Up Slow-Down (SUSD). O sistema opera como um loop agêntico iterativo consistindo de três componentes principais:

A. Inicialização Baseada em LLM (Raciocínio Semântico)

O processo começa com o LLM gerando uma alocação de tarefas inicial ($A_{LLM}$).

• Papel: O LLM atua como um "planejador guiado cognitivamente", interpretando descrições de tarefas em linguagem natural e capacidades dos robôs para produzir uma solução de "aquecimento" (warm start) viável.
• Entrada: Declarações de tarefas em linguagem natural, descrições de robôs e informações posicionais.
• Mecanismo: O sistema utiliza um método de serialização baseado em coordenadas para mapear dados espaciais contínuos no espaço de tokens discretos do LLM.
• Prompting: Um prompt estruturado inclui definição de papel, restrições rígidas (viabilidade), restrições flexíveis (compatibilidade) e diretrizes de formatação (saída do tipo JSON). O LLM é explicitamente incumbido de fornecer correspondências semânticas de alto nível, em vez de otimização numérica precisa.

B. Refinamento Probabilístico Baseado em SUSD (Otimização Numérica)

A alocação inicial é passada para o algoritmo SUSD para refinamento local.

• Natureza: O SUSD é um método de otimização bioinspirado e livre de derivadas baseado no comportamento de cardumes de peixes. É projetado para lidar com funções objetivo sem gradientes e para navegar em ruídos e ótimos locais.
• Processo: O algoritmo modela a matriz de alocação como uma distribuição de probabilidade. Ele atualiza iterativamente os parâmetros da distribuição usando uma regra de feedback baseada em velocidade que alinha a direção de busca principal com o declive mais íngreme da função objetivo.
• Garantia: O método garante que a solução refinada ($A_{SUSD}$) seja pelo menos tão boa quanto a proposta inicial do LLM ($F(A^*) \leq F(A_{LLM})$).

C. Loop de Feedback Guiado por Memória (Aprendizado em Contexto)

Uma inovação fundamental é o uso de um buffer de memória para facilitar o aprendizado em contexto sem atualizar os parâmetros do modelo.

• Mecanismo: Após cada iteração, a tupla da proposta inicial do LLM, a solução refinada pelo SUSD e o makespan resultante são armazenados em um buffer de memória ($H_t$).
• Recuperação: Para iterações subsequentes, o sistema recupera os registros históricos top-$n$ (baseados em desempenho) e os injeta no prompt do LLM como feedback estruturado de "antes/depois".
• Aprendizado: Isso permite que o LLM identifique padrões (ex: reduzir segmentos longos de deslocamento, equilibrar cargas de tarefas) e ajuste seu raciocínio semântico futuro para evitar ineficiências anteriores, simulando efetivamente um agente que refina sua política heurística ao longo do tempo.

3. Principais Contribuições

1. Estrutura Agêntica Híbrida: O artigo propõe uma arquitetura inovadora que combina as capacidades de raciocínio semântico de LLMs com a precisão numérica de busca local livre de derivadas (SUSD), preenchendo a lacuna entre planejamento de alto nível e otimização de baixo nível.
2. Aprendizado em Contexto Guiado por Memória: Os autores introduzem um mecanismo de feedback onde resultados de otimização históricos são usados para guiar a próxima geração do LLM via engenharia de prompt. Isso permite que o sistema aprenda com experiências bem-sucedidas e escape de ótimos locais sem exigir o ajuste fino (fine-tuning) ou atualizações de parâmetros do modelo.
3. Estratégia de Inicialização Escalável: O trabalho demonstra que os LLMs podem servir como geradores eficazes de "warm start" para problemas combinatórios, fornecendo soluções iniciais superiores em comparação com a inicialização aleatória ou heurística, acelerando assim a convergência.

4. Resultados Experimentais

O sistema foi avaliado em dois cenários distintos: inspeção subaquática de pequena escala (AUVs) e entrega urbana de drones de grande escala (UAVs).

• Melhoria de Desempenho: Comparado ao SUSD tradicional com inicialização aleatória, o método proposto reduziu o makespan médio da missão em 17,07%. Também superou Algoritmos Genéticos (GA), Otimização por Enxame de Partículas (PSO) e métodos de alocação baseados em mercado, com melhorias médias de 10,22%, 21,64% e 8,40%, respectivamente.
• Comparação com Solvers Exatos: Em instâncias de pequena escala onde solvers de Programação Linear Inteira Mista (MILP) puderam encontrar ótimos globais, o método proposto alcançou soluções próximas do ótimo, muitas vezes superando as alocações baseadas em solvers em 13,12% (atribuído a timeouts de solver ou cortes heurísticos em instâncias complexas).
• Estudos de Ablação:
  • Inicialização: A inicialização baseada em LLM forneceu consistentemente um ponto de partida melhor do que a redistribuição aleatória ou troca de tarefas, levando a uma convergência mais rápida.
  • Tamanho da Memória: O aumento do tamanho do buffer de memória melhorou o desempenho, com retornos decrescentes observados após a retenção das 5 melhores soluções históricas ($n=5$).
• Escalabilidade: A análise computacional revelou que o tempo de inferência do LLM permanece relativamente estável (perfil plano) mesmo quando o número de tarefas aumenta cinco vezes. O gargalo computacional primário é a etapa de otimização SUSD, que escala linearmente.

5. Significância e Alegações

O artigo afirma que esta abordagem neuro-simbólica oferece um avanço significativo no MRTA ao:

• Aumentar a Adaptabilidade: A capacidade de interpretar linguagem natural e lidar com especificações de tarefas ambíguas torna o sistema adequado para cenários com humanos no ciclo (human-in-the-loop), onde usuários não treinados fornecem objetivos de alto nível.
• Equilibrar Exploração e Explotação: A natureza híbrida permite que o LLM explore o espaço de soluções semanticamente enquanto o SUSD explota gradientes numéricos para precisão numérica.
• Eficiência: O método alcança soluções de alta qualidade com redução de variância e taxas de convergência mais rápidas em comparação com metaheurísticas tradicionais.

Os autores notam modestamente limitações, incluindo a implementação sequencial atual do SUSD (que limita o potencial de aceleração por GPU) e a dependência de prompts cuidadosamente estruturados. Eles sugerem que trabalhos futuros devem focar na paralelização do algoritmo SUSD, no desenvolvimento de "LLM na Borda" (Edge) para operação descentralizada e na integração de algoritmos evolutivos para adaptabilidade dinâmica de longo prazo.