💻 computer science

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space

COAgents introduz um framework multiagente cooperativo que modela o espaço de busca do Problema de Roteamento de Veículos como um grafo construído dinamicamente para separar o controle de busca agnóstico ao problema da codificação específica do domínio, alcançando desempenho de ponta entre métodos baseados em aprendizado em benchmarks de VRPTW ao reduzir significativamente a lacuna em relação às melhores soluções conhecidas.

Autores originais: Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

Publicado 2026-05-21

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um gerente de logística tentando descobrir a maneira mais eficiente para uma frota de caminhões de entrega visitar 100 casas diferentes. Este é um clássico "Problema de Roteamento de Veículos". O problema? Existem tantas rotas possíveis que até os supercomputadores mais rápidos não conseguem verificá-las todas. É como tentar encontrar o único melhor caminho através de um labirinto massivo e nebuloso, onde cada curva que você toma pode levar a um beco sem saída.

Por décadas, os humanos resolveram isso escrevendo manuais de regras rígidos: "Se você vir uma casa à esquerda, vire à direita". Mas esses manuais são frágeis. Se o layout da cidade mudar ligeiramente, as regras quebram, e especialistas precisam gastar semanas reescrevendo-as.

Aí entram os COAgents, um novo sistema criado por pesquisadores da Huawei. Em vez de um manual de regras rígido, os COAgents usam uma equipe de três "detetives de IA" que trabalham juntos para explorar o labirinto, aprender com seus erros e encontrar caminhos melhores do que nunca.

Veja como funciona, usando analogias simples:

1. O Mapa do Labirinto: O "Grafo de Busca Parcial"

Imagine que a IA não está apenas olhando para a rota atual; ela está desenhando um mapa de cada caminho que ela já tentou.

Nós (Os Pontos): Cada ponto no mapa é uma rota de entrega específica que a IA testou.
Arestas (As Linhas): As linhas conectando os pontos mostram como a IA passou de uma rota para a próxima (por exemplo, "Troçamos duas casas na rota").
A parte "Parcial": A IA não pode desenhar o labirinto inteiro infinito, então ela mantém apenas um mapa "parcial" das partes interessantes que visitou até agora. Este mapa é a memória compartilhada da equipe.

2. Os Três Agentes de IA

A mágica acontece porque três agentes de IA diferentes olham para este mapa e tomam decisões diferentes, assim como uma equipe esportiva com funções específicas:

O Escoteiro (Agente de Seleção de Nós):
- Função: "Qual rota devemos olhar a seguir?"
- Analogia: Imagine que você está em uma biblioteca com milhares de livros. O Escoteiro não escolhe um livro ao acaso. Ele olha para seu "histórico de leitura" (o mapa) e diz: "Ei, aquela rota ali parece promissora; está perto de uma boa solução. Vamos focar naquela." Isso impede que a equipe desperdice tempo em becos sem saída.
O Mecânico (Agente de Seleção de Movimentos):
- Função: "Como melhoramos esta rota específica?"
- Analogia: Assim que o Escoteiro escolhe uma rota, o Mecânico entra em ação. Ele tem uma caixa de ferramentas de truques (como trocar duas paradas ou reordenar uma rua). Ele olha para a rota atual e diz: "Se trocarmos essas duas casas, o caminhão economiza 5 minutos. Vamos fazer isso!" Ele é o especialista em fazer melhorias pequenas e locais.
O Explorador (Agente de Salto):
- Função: "Estamos presos! Vamos tentar algo totalmente novo."
- Analogia: Às vezes, o Escoteiro e o Mecânico ficam presos em um loop, fazendo melhorias minúsculas que realmente não ajudam. Eles estão presos em um "vale local". O Explorador é o agente que diz: "Esqueça este caminho. Vamos pular para uma parte completamente diferente do mapa." Ele gera uma rota totalmente nova do zero com base no que aprendeu no passado, ajudando a equipe a escapar da armadilha e encontrar um vale melhor.

3. Como Eles Trabalham Juntos

O processo é um ciclo contínuo:

O Escoteiro escolhe uma rota do mapa de histórico.
O Mecânico tenta ajustá-la para torná-la melhor.
Se eles continuarem ajustando e não estiverem ficando muito melhores, o Explorador entra, cria uma rota fresca e a adiciona ao mapa.
A equipe repete isso até que o tempo acabe.

Por Que Isso é Importante

O artigo afirma que essa abordagem baseada em equipe é um divisor de águas, especialmente para problemas difíceis como VRPTW (onde os caminhões têm janelas de tempo rígidas, como "deve chegar entre 14:00 e 14:30").

Superando o Melhor: Nestes testes difíceis, os COAgents superaram os melhores solucionadores de IA anteriores por uma margem significativa. Por exemplo, com 100 paradas, ele reduziu a lacuna para a solução perfeita em 14% em comparação com a IA anterior mais forte, e em 44% em comparação com outro método de topo.
Aprendizado vs. Regras: Ao contrário dos métodos antigos que dependem de regras escritas por humanos, os COAgents aprendem como pesquisar. Eles não precisam que um humano lhes diga como consertar um problema específico; eles descobrem a melhor estratégia olhando para seu próprio histórico.
Adaptabilidade: Como o "cérebro" (os agentes) é separado das "regras do jogo" (o layout específico da cidade), você pode facilmente trocar as regras do jogo (por exemplo, mudar de caminhões de entrega para entrega por drones) sem reconstruir toda a IA.

A Troca

O artigo é honesto sobre uma desvantagem: Velocidade.
Como os COAgents estão constantemente desenhando seu mapa, verificando o histórico e executando três agentes diferentes, leva mais tempo para executar do que alguns métodos mais simples e rápidos que apenas constroem uma rota uma vez e param. No entanto, os autores argumentam que, para os problemas mais difíceis onde encontrar a melhor solução importa mais do que a velocidade, esse tempo extra vale a pena.

Em resumo: Os COAgents são como uma equipe inteligente e colaborativa de exploradores que mantém um diário detalhado de sua jornada. Em vez de adivinhar cegamente ou seguir um manual de regras estático, eles usam seu histórico compartilhado para saber quando cavar mais fundo, quando ajustar seu caminho e quando dar um salto gigante para um novo território, encontrando, em última análise, soluções melhores do que qualquer outra pessoa antes.

Resumo Técnico: COAgents – Framework Multi-Agente para Problemas de Roteamento

Declaração do Problema

Problemas de Roteamento de Veículos (VRPs), incluindo o Problema de Roteamento de Veículos com Capacidade (CVRP) e o Problema de Roteamento de Veículos com Janelas de Tempo (VRPTW), são centrais para logística e manufatura, mas permanecem computacionalmente intratáveis em escala devido à sua complexidade combinatória. Métodos heurísticos tradicionais dependem de regras artesanais para melhorias locais e diversificação (saltos) para escapar de mínimos locais. No entanto, esses conjuntos de regras estáticas frequentemente carecem de generalização entre instâncias diversas, exigem extensa expertise de domínio para ajuste e não conseguem adaptar-se a distribuições de problemas em evolução. Embora abordagens "Aprender a Buscar" (L2S) tenham surgido, muitas focam exclusivamente na seleção de operadores ou decisões de estado atual, sem modelar efetivamente o histórico de busca ou a estrutura mais ampla do espaço de busca.

Metodologia: O Framework COAgents

Os autores propõem COAgents, um framework multi-agente cooperativo que modela o processo de busca do VRP como uma travessia de grafo. A inovação central é o Grafo de Busca Parcial (PSG), um subgrafo dinamicamente construído onde os nós representam soluções exploradas e as arestas representam movimentos locais ou grandes perturbações (saltos).

1. O Grafo de Busca Parcial (PSG)

O PSG serve como uma codificação de estado consciente do histórico. É um grafo direcionado e desconexo onde:

Nós: Representam soluções individuais encontradas durante a busca.
Arestas: Representam movimentos de vizinhança (refinamentos locais) ou saltos (grandes perturbações).
Estrutura: O grafo decompõe-se em componentes conectados (amostras), cada um explorando a vizinhança de um ótimo local. Essa estrutura permite que o sistema rastreie a trajetória da busca e identifique padrões na exploração.

2. Arquitetura Multi-Agente

O COAgents emprega três agentes aprendidos operando sobre o PSG, todos compartilhando uma espinha dorsal neural comum composta por Redes de Convolução Gráfica com Portões (GGCN) e Transformers:

Agente de Seleção de Nós (NSA): Seleciona uma solução candidata (nó) do PSG para servir como incumbente para a próxima etapa de busca local. Prioriza regiões promissoras do espaço de busca com base em dados históricos.
Agente de Seleção de Movimento (MSA): Prevê o operador de vizinhança (movimento) mais promissor a aplicar na solução selecionada, impulsionando a intensificação local.
Agente de Salto (JA): Acionado quando a busca estagna (indicado por tentativas falhas repetidas), este agente gera uma solução completamente nova do zero com base no histórico de busca. Diferentemente de operadores padrão, o Agente de Salto realiza um reinício aprendido para escapar de mínimos locais e direcionar a busca para regiões inexploradas.

3. Arquitetura do Modelo e Treinamento

Codificação: Soluções são codificadas em características de nó ( $u_i$ ) capturando atributos globais (valor objetivo, viabilidade) e matrizes de estrutura interna ( $V_i$ ). Incorporações posicionais são derivadas via codificadores de passeio aleatório para a estrutura do PSG e codificadores específicos do problema para a topologia da solução.
Blocos Centrais: A rede utiliza camadas GGCN intercaladas para capturar padrões estruturais locais dentro do PSG e camadas Transformer para modelar dependências de longo alcance entre todos os nós. Módulos Específicos do Problema de Ponta a Ponta (E2E) refinam a estrutura interna do problema combinatório.
Treinamento:
- NSA e MSA: Treinados conjuntamente como tarefas de classificação binária para identificar a solução mais próxima do ótimo e o melhor próximo movimento, respectivamente, minimizando a entropia cruzada binária conjunta.
- Agente de Salto: Treinado separadamente para prever uma matriz de adjacência estocástica representando uma nova solução. É treinado contra um conjunto de soluções de referência quase ótimas para reduzir a ambiguidade de rótulos.
Inferência: O framework executa um loop onde o NSA seleciona um nó, o MSA seleciona um movimento e o PSG é atualizado. Se ocorrer estagnação, o JA é invocado. Isso continua até que um orçamento computacional (tempo ou limite de nós) seja atingido.

Contribuições Principais

Agentes Aprendidos Novos: Introdução do Agente de Seleção de Nós e do Agente de Salto, juntamente com um Agente de Seleção de Movimento. Esses agentes substituem coletivamente regras artesanais, permitindo políticas de decisão adaptativas e orientadas por dados para seleção de soluções, aplicação de operadores e diversificação.
Arquitetura Unificada com Pesos Compartilhados: Todos os agentes compartilham uma espinha dorsal neural comum, facilitando treinamento eficiente em dados, transferibilidade para novas variantes de problemas e redução da necessidade de ajuste por especialistas.
Representação do Grafo de Busca Parcial: Formalização do PSG como uma codificação de estado geral e consciente do histórico que impulsiona decisões dos agentes, distinguindo a abordagem de métodos que dependem exclusivamente do estado atual.
Framework Adaptativo a Solucionadores e Problemas: O COAgents envolve rotinas de busca local existentes e solucionadores neurais, aprimorando-os com políticas adaptativas que se adaptam perfeitamente a diferentes variantes de VRP.

Resultados Experimentais

O framework foi avaliado em benchmarks de CVRP e VRPTW usando 10.000 instâncias de treinamento e conjuntos de teste padrão (por exemplo, 1.000 instâncias de VRPTW).

Desempenho em VRPTW: O COAgents estabeleceu um novo estado da arte entre métodos baseados em aprendizado.
- Reduziu a lacuna de otimalidade em relação às melhores soluções conhecidas em 14% (em N=100) e 44% (em N=50) em relação ao solucionador neural mais forte (POMO).
- Reduziu a lacuna em 21% (N=100) e 40% (N=50) em relação à Busca de Vizinhança Grande Adaptativa (ALNS).
- Superou todas as bases neurais, OR-Tools e ALNS no conjunto de teste VRPTW.
Desempenho em CVRP: O COAgents permaneceu competitivo com bases de estado da arte de aprender a buscar, demonstrando eficácia mesmo com um módulo de codificação compacto e específico do problema.
Estudo de Ablação: Remover o Agente de Salto quase dobrou a lacuna de otimalidade (de 3,7% para 7,8%), destacando seu papel crítico em escapar de mínimos locais. Os agentes de Seleção de Nós e de Movimento também contribuíram significativamente para o desempenho.
Comparação com ALNS: Mesmo quando o ALNS teve acesso a um conjunto maior de operadores artesanais (incluindo 27 pares adicionais de destruição-reparação), o COAgents consistentemente o superou, validando a superioridade de políticas aprendidas sobre heurísticas estáticas.

Significado e Alegações

O artigo afirma que o COAgents representa uma mudança significativa de heurísticas estáticas e artesanais para sistemas multi-agentes adaptativos que aprendem com o histórico de busca. Ao modelar explicitamente o espaço de busca como um grafo e utilizar um Grafo de Busca Parcial, o framework permite que os agentes tomem decisões informadas sobre intensificação e diversificação que métodos tradicionais não conseguem alcançar.

Os autores posicionam o COAgents como uma alternativa convincente a heurísticas clássicas e métodos existentes de aprender a construir/buscar, particularmente para problemas complexos como VRPTW, onde generalização e adaptabilidade são cruciais. Embora reconheçam que a implementação atual em Python é mais lenta do que heurísticas baseadas em C/C++ (como LKH3 e HGS) e que a escalabilidade para instâncias muito grandes permanece um desafio devido aos custos quadráticos de atenção, o framework demonstra que o controle de busca aprendido e consciente do histórico pode reduzir significativamente a lacuna em relação às melhores soluções conhecidas em problemas de roteamento.