Adaptive Obstacle-Aware Task Assignment and Planning for Heterogeneous Robot Teaming

1. Problema Definido

O artigo aborda os desafios do Planejamento e Atribuição de Tarefas Multiagente (MATP) em ambientes ricos em obstáculos e dinâmicos, especificamente para equipes de robôs heterogêneos (com diferentes capacidades e tipos de robôs, como drones e robôs terrestres).

Os principais desafios identificados são:

• Escalabilidade e Raciocínio Espacial: Métodos existentes frequentemente falham em escalar ou não consideram adequadamente a distribuição de obstáculos ao agrupar tarefas, levando a atribuições subótimas.
• Adaptabilidade: A dificuldade de incorporar instruções humanas em tempo real durante a execução da missão.
• Heterogeneidade: Gerenciar restrições de capacidade e capacidades específicas de diferentes robôs simultaneamente.
• Interação Humano-Robô: A maioria dos sistemas atuais permite interação apenas antes da missão ou após falhas, não suportando replanejamento dinâmico baseado em comandos de linguagem natural durante a execução.

2. Metodologia: O Framework OATH

Os autores propõem o OATH (Adaptive Obstacle-Aware Task Assignment and Planning), um framework hierárquico que integra três componentes principais:

A. Mapeamento Adaptativo com Sequência de Halton

Para superar as limitações de mapas de grade tradicionais, o OATH introduz um Mapa de Sequência de Halton Adaptativo:

• Amostragem Consciente de Obstáculos: Diferente das sequências de Halton padrão (uniformes), este método ajusta a densidade de amostragem com base na proximidade de obstáculos.
• Função de Aceitação Probabilística: Pontos próximos a obstáculos têm maior densidade de amostragem (para garantir caminhos viáveis em áreas complexas), enquanto áreas abertas têm menor densidade.
• Cálculo de Distância: Utiliza o algoritmo de Dijkstra sobre este mapa adaptativo para calcular matrizes de distância entre tarefas que refletem a verdadeira viabilidade de travessia, evitando agrupar tarefas que parecem próximas geometricamente, mas estão separadas por paredes.

B. Framework Hierárquico de Atribuição (Cluster–Auction–Selection)

O sistema utiliza uma abordagem híbrida para equilibrar otimização e escalabilidade:

1. Agrupamento (Clustering): As tarefas são agrupadas usando agrupamento hierárquico aglomerativo baseado nas distâncias conscientes de obstáculos (não apenas Euclidianas).
2. Leilão Ponderado por Cluster (Cluster-Weighted Auction): Os robôs licitam por clusters de tarefas. A pontuação considera:
   • A distância do robô ao centro do cluster.
   • A compatibilidade entre as capacidades do robô e a composição de tipos de tarefas no cluster.
3. Seleção de Tarefas Intra-Cluster: Dentro do cluster atribuído, cada robô resolve um problema de roteamento local (semelhante ao Problema do Caixeiro Viajente - TSP) usando um solver de Programação Linear Inteira Mista (MILP) para otimizar a sequência de coleta e entrega, respeitando limites de capacidade e compatibilidade de tipos.

C. Integração com Grandes Modelos de Linguagem (LLMs)

O OATH integra um LLM como um interpretador persistente durante toda a execução:

• Tradução de Instruções: O LLM converte comandos de linguagem natural (ex: "Adicione uma nova tarefa no ponto X" ou "Há um novo obstáculo perto de Y") em estruturas de dados JSON estruturadas.
• Replanejamento em Tempo Real: O sistema atualiza o mapa, recalcula distâncias e reatribui tarefas dinamicamente sem interromper a execução.
• Interface Interativa: Se uma instrução for ambígua, o sistema solicita esclarecimentos ao operador humano antes de executar mudanças, garantindo robustez.

3. Principais Contribuições

1. Sequência de Halton Adaptativa: Primeira aplicação conhecida de amostragem de Halton com adaptação baseada em obstáculos no contexto de MATP, permitindo uma representação espacial mais fiel e eficiente.
2. Framework Hierárquico Heterogêneo: Uma estrutura de atribuição que generaliza para qualquer número de tipos de tarefas, reduzindo a complexidade computacional enquanto respeita restrições de capacidade e habilidades dos robôs.
3. Pipeline Online com LLM: Uma integração completa onde o LLM atua não apenas como planejador inicial, mas como um interpretador contínuo de instruções humanas, permitindo reações imediatas a mudanças no ambiente ou na missão.
4. Validação em Hardware e Simulação: Demonstração robusta em simuladores (NVIDIA Isaac Sim) e em experimentos reais com plataformas TurtleBot3, provando a viabilidade prática.

4. Resultados Experimentais

Os autores compararam o OATH com três baselines: CBBA (algoritmo de leilão baseado em consenso), K-means+Auction+NN (heurística simples) e K-means+Auction+MILP (sem consciência de obstáculos).

• Eficiência de Atribuição: O OATH demonstrou uma sensibilidade de complexidade muito menor que os baselines. Enquanto o tempo de execução de outros métodos crescia rapidamente com o aumento de tarefas ou robôs, o OATH manteve um crescimento mais suave.
• Desempenho End-to-End: O OATH reduziu o tempo total de missão em 27,4% em comparação com o CBBA, mesmo gastando um tempo ligeiramente maior na fase de atribuição. Isso ocorre porque as atribuições são mais realistas, evitando caminhos bloqueados por obstáculos.
• Qualidade da Solução vs. Tempo: Em comparação com um solver MILP global (Gurobi), o OATH sacrifica uma pequena porcentagem de otimalidade global (gap de ~13-24% em instâncias pequenas) em troca de um tempo de computação drasticamente menor (sub-segundo vs. minutos/horas), tornando-o viável para tempo real.
• Escalabilidade: O sistema escalou bem até 100 tarefas, mostrando crescimento quase linear no tempo total e no número de passos.
• Interação com LLM: O parser de LLM alcançou 100% de precisão para instruções de atualização de obstáculos. Instruções ambíguas foram tratadas com sucesso através de diálogos de esclarecimento.
• Validação em Hardware: Experimentos com quatro robôs TurtleBot3 confirmaram a estabilidade do sistema sob ruído de sensores, latência de comunicação e incertezas de cinemática, com replanejamento suave após a detecção de novos obstáculos via comando humano.

5. Significância e Impacto

O trabalho OATH representa um avanço significativo na robótica multiagente ao:

• Ponte entre Simulação e Realidade: Demonstra que algoritmos complexos de atribuição de tarefas podem ser executados com sucesso em hardware real, lidando com ruído e atrasos de comunicação.
• Acessibilidade Humana: Ao integrar LLMs, torna o controle de equipes de robôs complexos acessível a operadores humanos sem necessidade de programação técnica, permitindo intervenções dinâmicas em cenários imprevisíveis (como resgate ou logística em armazéns).
• Eficiência Espacial: A abordagem de amostragem adaptativa oferece uma nova maneira de lidar com a complexidade geométrica em ambientes de robótica, superando as limitações de mapas de grade tradicionais.

Em resumo, o OATH fornece uma solução robusta, escalável e adaptável para coordenar equipes heterogêneas de robôs em ambientes desafiadores, combinando otimização matemática rigorosa com a flexibilidade da inteligência artificial generativa.