Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

Resumo Técnico: Transporte Cooperativo Multiagente: Alocação de Tarefas e Busca de Caminhos Ótimas e Eficientes

Definição do Problema: CT-TAPF
Este artigo aborda uma lacuna crítica nas estruturas existentes de Busca de Caminhos Multiagente (MAPF) e de Alocação de Tarefas e Busca de Caminhos (TAPF): a incapacidade de lidar com tarefas de transporte cooperativo que exigem múltiplos agentes para mover um único objeto grande. Os autores formalizam o problema de Alocação de Tarefas e Busca de Caminhos para Transporte Cooperativo (CT-TAPF). Neste cenário, um conjunto de $n$ agentes deve ser atribuído a um conjunto de $m$ tarefas cooperativas. Cada tarefa $\tau_i$ requer um tamanho de equipe específico $k_i$ e envolve duas fases:

1. Fase de Montagem: Os agentes viajam independentemente para "slots" designados (vértices de configuração inicial) para formar uma equipe.
2. Fase de Comboio: Uma vez que todos os agentes atribuídos chegam e sincronizam, eles se movem como uma única entidade rígida (um "Comboio") até a configuração de destino.

O problema é NP-difícil, generalizando o TAPF. Uma solução válida deve minimizar a Soma dos Custos (SoC) enquanto garante caminhos livres de colisões. Crucialmente, o artigo introduz uma definição geométrica de conflito onde colisões ocorrem se as pegadas dos agentes ou comboios se sobrepuserem, mesmo que suas posições de referência sejam distintas.

Metodologia
Os autores propõem uma arquitetura de busca de dois níveis para resolver o CT-TAPF, introduzindo tanto um solucionador ótimo quanto uma família de variantes sub-ótimas.

1. Solucionador Ótimo: CT-TCBS
   A Busca Baseada em Conflitos para Alocação de Tarefas de Transporte Cooperativo (CT-TCBS) é um algoritmo de dois níveis baseado na estrutura de Busca Baseada em Conflitos (CBS):

   • Busca de Alto Nível: Realiza uma busca A* em uma árvore de restrições. Cada nó representa uma solução parcial definida por atribuições de tarefas e restrições espaço-temporais. O algoritmo prioriza a resolução de conflitos de caminho antes de atribuir novas tarefas.
   • Planejador de Baixo Nível: Utiliza um A* Unificado para calcular caminhos ótimos para agentes individuais e comboios multiagentes. Ele lida com a sincronização de agentes chegando aos slots de montagem e planeja o movimento conjunto do comboio.
   • Estratégia de Expansão Incremental: Uma contribuição central é a substituição da "Expansão Combinatória" (que gera todas as permutações possíveis de equipes de uma só vez) pela Expansão Incremental. Em vez de atribuir uma equipe completa imediatamente, o algoritmo atribui agentes aos slots de tarefa um por um. Isso cria nós intermediários, parcialmente atribuídos, reduzindo drasticamente o fator de ramificação e gerenciando a explosão combinatória inerente à formação de equipes.
   • Função Heurística: A heurística $H$ é a soma de dois componentes admissíveis: $H_1$ (custo de transporte comprometido para agentes parcialmente atribuídos) e $H_2$ (custo de atribuição estimado para slots não atribuídos). Os autores excluem explicitamente um componente de tempo de espera de sincronização ($H_3$) porque calcular um limite inferior admissível para ele é computacionalmente intratável (equivalente ao Problema de Atribuição Generalizado).

2. Solucionadores Sub-Ótimos: Seletores Centrados na Tarefa
   Para abordar a escalabilidade, os autores desenvolvem variantes sub-ótimas que introduzem uma perspectiva global centrada na tarefa. Diferentemente das abordagens centradas no agente do tipo "vizinho mais próximo" (que podem levar a uma formação de equipe ineficiente), esses solucionadores selecionam a próxima tarefa a ser atribuída com base em uma métrica global de dificuldade:

   • Melhor Tarefa (BT): Seleciona a tarefa com o menor custo estimado de conclusão (abordagem gananciosa).
   • Pior Tarefa (WT): Seleciona a tarefa com o maior custo estimado de conclusão (abordagem de falha rápida), visando formar equipes complexas cedo para evitar impasses.
     Esses solucionadores utilizam o algoritmo húngaro para estimar a dificuldade da tarefa com base na disponibilidade dos agentes e nos tempos de viagem.

Principais Descobertas e Resultados
Através de uma avaliação empírica abrangente em mapas de grade com densidades e distribuições de tarefas variadas, o artigo relata três descobertas principais:

1. Superioridade da Expansão Incremental: A estratégia de Expansão Incremental supera significativamente a abordagem Combinatória ingênua. A análise estatística confirma que o ônus combinatório da alocação de tarefas é o gargalo computacional dominante, e não os conflitos de busca de caminhos. Ao podar o espaço de busca de alocação de tarefas, a estratégia incremental alcança taxas de sucesso significativamente mais altas.
2. O Dilema Expansão de Conflito de Tarefas: O artigo identifica um fenômeno contra-intuitivo onde estratégias sofisticadas de resolução de conflitos (especificamente MAX-d, que é eficaz para MAPF de Grandes Agentes) performam pior no cenário integrado CT-TAPF. Os autores atribuem isso ao "Dilema Tarefa-Conflito": a estratégia do MAX-d de aumentar os custos dos nós para podar árvores de conflito força a busca de alto nível a explorar mais ramos de alocação de tarefas prematuramente, levando a espaços de busca maiores e taxas de sucesso menores dentro dos limites de tempo.
3. Nova Fronteira de Eficiência: Os solucionadores sub-ótimos propostos (particularmente a variante Pior Tarefa) estabelecem uma nova fronteira de compromisso entre a qualidade da solução e o tempo de execução. Embora o CT-TCBS Ótimo forneça as melhores soluções, ele é computacionalmente caro. Os solucionadores sub-ótimos superam as bases centradas no agente (como -nn1/-nn2) ao encontrar soluções de maior qualidade mais rapidamente, enquanto são mais robustos do que heurísticas gananciosas simples. Especificamente, o seletor WT geralmente produz soluções mais próximas do ótimo do que o BT, pois prioriza a formação de equipes complexas cedo, impedindo que os agentes se dispersem.

Significado e Alegações
O artigo alega fornecer uma estrutura fundamental para uma nova classe de problemas cooperativos multiagente. Seu significado reside em:

• Formalização do CT-TAPF: Ir além da execução individualista de tarefas para modelar ações cooperativas sustentadas e fisicamente acopladas.
• Inovação Algorítmica: Introduzir a estratégia de Expansão Incremental para gerenciar a explosão combinatória específica da formação de equipes, que solucionadores TAPF padrão não conseguem lidar eficientemente.
• Escalabilidade Prática: Oferecer um conjunto de algoritmos (do ótimo ao sub-ótimo) que permitem aos praticantes navegar pelo compromisso entre otimalidade da solução e viabilidade computacional em cenários logísticos do mundo real envolvendo mercadorias grandes ou irregulares.

Os autores concluem que, embora sua estrutura atual seja discreta, trabalhos futuros expandirão esses conceitos para domínios contínuos e agentes heterogêneos, mas a contribuição atual estabelece a base teórica e algorítmica necessária para o transporte cooperativo.