Resumo Técnico: Otimização por Colônia de Formigas de Bi-Camada para Alocação de Tarefas e Roteamento de Multi-Robôs

Definição do Problema

O artigo aborda o problema de Alocação de Tarefas Multi-Robô (MRTA) no contexto de aplicações de entrega e logística. O desafio central envolve coordenar uma frota de robôs móveis para executar um conjunto de tarefas de entrega, onde cada tarefa consiste em um local de coleta específico e um local de entrega.

O problema de otimização é definido como um processo de decisão acoplado que requer duas saídas simultâneas:

1. Atribuição de Tarefas: Determinar qual robô realiza cada tarefa específica.
2. Sequenciamento de Tarefas: Determinar a ordem ideal na qual um robô executa suas tarefas atribuídas.

O objetivo é minimizar a distância total percorrida de toda a frota, garantindo que cada tarefa seja executada exatamente uma vez por um único robô. Os autores observam que as abordagens existentes frequentemente tratam a atribuição, o sequenciamento e a execução como estágios independentes otimizados separadamente. Essa separação pode levar a uma coordenação global subótima, movimento redundante e redução da eficiência do sistema. O artigo formula o MRTA como um problema de otimização unificado, onde as decisões de atribuição e sequenciamento são interdependentes.

Metodologia: Otimização por Colônia de Formigas (ACO) de Bi-Camada

Para resolver o problema de otimização formulado, os autores propõem um algoritmo de Otimização por Colônia de Formigas (ACO) de Bi-Camada. Diferente dos métodos hierárquicos tradicionais que resolvem as camadas sequencialmente, esta abordagem integra duas camadas de decisão interdependentes em um único processo de colônia.

Estrutura Central

O algoritmo emprega uma metaheurística baseada em população inspirada no comportamento de forrageamento de formigas. Cada "formiga" na colônia constrói uma solução completa navegando simultaneamente por duas camadas de decisão:

1. Camada de Atribuição de Tarefas:

   • Determina a alocação de tarefas aos robôs ($x_{i,j}$).
   • Utiliza uma matriz de feromônio $\tau_{assign} \in \mathbb{R}^{m \times n}$ (tarefas $\times$ robôs) que representa a desejabilidade aprendida de atribuir a tarefa $j$ ao robô $i$.
   • A informação heurística ($\eta_{assign}$) é derivada do inverso da distância entre a posição inicial do robô e o local de coleta da tarefa.

2. Camada de Sequenciamento de Tarefas:

   • Determina a ordem de visita ($\pi_i$) para as tarefas atribuídas a cada robô.
   • Utiliza uma matriz de feromônio $\tau_{seq} \in \mathbb{R}^{m \times m}$ que representa a desejabilidade de transicionar da tarefa $j$ para a tarefa $k$ dentro da rota do mesmo robô.
   • A informação heurística ($\eta_{seq}$) é derivada do inverso da distância entre o ponto de entrega da tarefa atual e a coleta da próxima tarefa.

Execução do Algoritmo

O algoritmo procede através de ciclos iterativos:

1. Construção: Cada formiga atribui tarefas aos robôs probabilisticamente com base nos valores de feromônio e heurística da camada de atribuição. Uma vez feitas as atribuições, a camada de sequenciamento constrói a rota para cada robô. A primeira tarefa é selecionada com base na proximidade com o início do robô, e as tarefas subsequentes são amostradas com base no feromônio de sequenciamento e nos valores heurísticos.
2. Avaliação: A distância total percorrida para a solução construída é calculada, somando as distâncias de todos os robôs (início-até-coleta, coleta-até-entrega e entrega-até-próxima-coleta).
3. Atualização de Feromônio: Após todas as formigas construírem suas soluções, os rastros de feromônio em ambas as matrizes são atualizados. Isso envolve:
   • Evaporação: Redução dos níveis de feromônio existentes para evitar estagnação.
   • Reforço: Deposição de novo feromônio proporcional à qualidade da solução ($Q/C(a)$), onde melhores soluções (menor custo) depositam mais feromônio. As equações de atualização garantem que tanto os pares de atribuição quanto as transições específicas de tarefas na rota sejam reforçados.

Principais Contribuições

O artigo identifica as seguintes contribuições primárias:

• Função Objetivo Unificada: A formulação de uma nova função de custo que transforma o MRTA em um problema de otimização acoplado, capturando explicitamente a interdependência entre a distribuição global de tarefas e o planejamento de rota local.
• Arquitetura ACO de Bi-Camada: A introdução de um novo framework algorítmico que integra atribuição e sequenciamento em um único processo de colônia usando duas matrizes de feromônio distintas e interconectadas. Isso permite a otimização simultânea da alocação de tarefas e do planejamento de rotas.
• Validação de Desempenho: Experimentos comparativos abrangentes demonstrando a eficácia do método proposto contra Programação Linear Inteira Mista (MILP) e Otimização por Enxame de Partículas (PSO).

Resultados Experimentais

O método proposto foi avaliado em um ambiente de simulação ROS 2 Humble e Gazebo utilizando três robôs TurtleBot3. Os experimentos foram conduzidos em três cenários com 5, 10 e 20 tarefas.

Métricas de Desempenho:

• Distância Total Percorrida: O Bi-Layer ACO alcançou consistentemente a menor distância média total de percurso em todos os tamanhos de tarefas.
  • Comparado ao MILP, o ACO reduziu a distância total em aproximadamente 17,7% (com 5 tarefas).
  • Comparado ao PSO, o ACO reduziu a distância total em aproximadamente 9,8%.
• Tempo de Conclusão: O método proposto também demonstrou tempos de conclusão de tarefas mais rápidos.
  • Comparado aos métodos de base, o ACO reduziu o tempo de conclusão em quase 20%.
• Estabilidade e Escalabilidade:
  • O ACO exibiu desvios padrão menores tanto em distância quanto em tempo comparado ao PSO e MILP, indicando uma convergência mais estável.
  • À medida que a complexidade das tarefas aumentava (até 20 tarefas), o ACO manteve um desempenho superior, enquanto o MILP e o PSO mostraram maior dispersão e custos mais elevados.

Significância e Alegações

O artigo afirma que o framework Bi-Layer ACO aborda efetivamente a limitação de separar a atribuição de tarefas e o roteamento nas abordagens de MRTA existentes. Ao otimizar essas decisões conjuntamente, o método reduz o movimento redundante e melhora a eficiência geral da missão.

Os autores concluem que o Bi-Layer ACO é uma solução escalável e confiável para tarefas de entrega multi-robô, oferecendo um equilíbrio entre exploração e explotação que produz rotas mais curtas e consistentes do que os métodos exatos tradicionais (MILP) ou outras meta-heurísticas (PSO). O trabalho sugere que esta abordagem unificada é particularmente valiosa para aumentar a eficiência de sistemas de logística e entrega do mundo real. O trabalho futuro foca na extensão da abordagem para ambientes dinâmicos, frotas de robôs heterogêneos e restrições de comunicação.