Resumo Técnico: ChronoForest

Definição do Problema

O artigo aborda o desafio do planejamento de rotas offline de longo horizonte onde apenas trajetórias offline de curto horizonte estão disponíveis. Neste cenário, um agente (ou múltiplos agentes) deve construir uma rota que alcance um objetivo designado, visite um conjunto compartilhado de pontos de passagem (waypoints) e minimize o custo total da rota, apesar de carecer de custos de viagem par a par pré-computados entre os âncoras (início, objetivo e waypoints).

O problema apresenta duas dificuldades acopladas:

1. Nível Microscópico (Busca de Pontes/Bridge Search): Compor muitos segmentos de curto horizonte cria um compromisso entre o custo de busca e a qualidade do caminho. Pesquisar mais candidatos pode encontrar pontes mais curtas, mas aumenta os custos de inferência, enquanto o compromisso precoce pode resultar em caminhos viáveis, porém subótimos. Os planejadores baseados em difusão existentes frequentemente otimizam para geração plausível em vez de encurtamento ativo de caminhos.
2. Nível Macroscópico (Composição de Rota): Determinar a ordem ideal dos waypoints (uma variante do Problema do Caixeiro Viajante Múltiplo, ou mTSP) requer a comparação de custos de viagem par a par. No entanto, esses custos são desconhecidos a priori e devem ser estimados online. Estimativas de distância temporal de longo alcance, frequentemente usadas para orientação, tornam-se cada vez mais pouco confiáveis à medida que o horizonte cresce, tornando inaplicáveis os métodos clássicos de roteamento que assumem matrizes de custo pré-computadas.

Metodologia: ChronoForest

Os autores propõem o ChronoForest, um sistema de planejamento de malha fechada (closed-loop) que acopla a busca de pontes local com o re-resolução de rotas online. O sistema opera através de dois módulos interativos:

1. Planejador de Difusão de Árvore de Encadeamento de Âncoras (Baixo Nível)

Este módulo é responsável por construir "pontes" curtas e viáveis entre pares de âncoras sob um orçamento de inferência limitado.

• Estrutura de Árvore: Mantém árvores de busca bidirecional enraizadas em cada âncora. Os nós armazenam prefixos materializados, custos cumulativos e segmentos locais representativos.
• Orientação por Distância Temporal: Utiliza uma representação de distância temporal aprendida ($d_{TD}$) para guiar o processo de difusão. Este escore estima a dificuldade de alcançar um objetivo e direciona a denoização para os nós alvo.
• Seleção de Alvo Condicionada ao Par: Diferente da orientação global, a seleção de alvo é condicionada ao par específico de âncoras ordenadas que está sendo expandido. Minimiza uma função de custo total estimada que combina o custo de chegada (cost-to-come) do lado da origem, um custo de contato baseado em distância temporal e o custo de prefixo do lado do alvo.
• Avaliação e Expansão de Nós: Os nós são classificados com base em uma combinação de eficiência de caminho (proximidade ao caminho mais curto) e incerteza (dispersão do ponto final). O planejador realiza a expansão seletiva e paralela dos nós de melhor classificação.
• Detecção de Junção: Um detector de junção gera, poda e agrupa subplanos de lookahead. Ele utiliza orientação de difusão condicionada ao alvo para direcionar os subplanos aos alvos atribuídos, garantindo que apenas representantes promissores e compactos sejam retidos para a próxima rodada.

2. Orquestrador Multi-Árvore Online (Alto Nível)

Este módulo gerencia a hipótese global da rota e aloca o orçamento de busca.

• Agregação de Evidência de Pontes: Mantém uma Matriz de Pontes Diretas ($C_t$) que armazena as melhores estimativas atuais de custo para pares de âncoras ordenados, baseadas na evidência coletada pelo planejador de baixo nível.
• Re-resolução de Rota: Usando o fechamento de todos os saltos de Floyd-Warshall ($\tilde{C}_t$) da matriz de pontes diretas, o orquestrador re-resolve repetidamente a rota conjunta tentativa. Isso permite que o sistema atualize a hipótese da rota conforme novas evidências de pontes tornam-se disponíveis.
• Alocação de Orçamento: O orquestrador divide o orçamento de expansão em duas categorias:
  • Exploração da Rota Atual: Prioriza a expansão de adjacências na rota tentativa atual para refinar suas estimativas de custo.
  • Cobertura Fora da Rota: Aloca um pequeno orçamento para pares com evidências ausentes ou não certificadas para garantir a conectividade global.
• Aceitação Suave (Soft Acceptance): Um encontro adjacente à rota é "aceito suavemente" se preservar a compatibilidade com a rota atual, permitindo que o sistema ajuste dinamicamente a rota conforme melhores pontes são descobertas.

Principais Contribuições

1. Formalização: O artigo formaliza um cenário de navegação acoplado ao mTSP onde o planejamento de waypoints de longo horizonte e o roteamento devem ser resolvidos conjuntamente a partir de dados offline de curto horizonte sem uma matriz de custo par a par pré-computada.
2. Arquitetura do Sistema: Introduz o ChronoForest, um sistema de malha fechada que acopla um planejador de difusão baseado em árvore com um orquestrador online. O sistema usa distância temporal para orientação local, enquanto depende da evidência de pontes acumulada para validar a conectividade de longo alcance e re-resolver a rota.
3. Eficiência e Qualidade: A abordagem demonstra que a re-resolução de rotas online pode corrigir ordenações temporais ruins e melhorar a qualidade da rota sem incorrer no custo de um planejamento exaustivo.

Resultados Experimentais

O método foi avaliado no benchmark OGBench AntMaze-Stitch e em tarefas de composição de rota Hamiltoniana.

• Taxas de Sucesso: No benchmark AntMaze-Stitch, o ChronoForest alcançou taxas de sucesso de 99,8% (Médio), 99,3% (Grande) e 99,5% (Gigante).
• Melhoria sobre o SOTA: No desafiador split "Gigante", o ChronoForest melhorou o sucesso em 34,5 pontos percentuais em relação ao melhor planejador baseado em difusão anterior (CompDiffuser).
• Eficiência da Rota: Em análises de planejamento Hamiltoniano, o mecanismo de re-resolução online reduziu significamente os comprimentos totais das rotas em comparação ao uso de uma ordenação de distância temporal fixa, aproximando-se do desempenho de uma referência "graficamente fixa" privilegiada.
• Eficiência Computacional: O ChronoForest alcançou esses ganhos de qualidade de rota com um custo de planejamento (tempo e nós expandidos) substancialmente menor do que a busca exaustiva, demonstrando que os ganhos não são meramente resultado de geração de candidatos por força bruta.

Significância e Alegações

O artigo alega que a composição de rotas de longo horizonte se beneficia mais do acoplamento da busca de pontes local guiada por distância temporal com a re-resolução explícita de rotas online.

• Abordando o Hiato de Horizonte: Ao usar difusão de fragmentos curtos dentro de um loop baseado em árvore, o sistema extrapola efetivamente além do horizonte de treinamento sem exigir dados de treinamento de longo horizonte.
• Estimativa Dinâmica de Custo: O sistema supera a falta de confiabilidade das estimativas de distância temporal de longo alcance ao tratá-las apenas como orientação local, enquanto valida a conectividade de longo alcance através de busca em múltiplas árvores bidirecionais e re-resolução iterativa de rotas.
• Eficiência Prática: Os resultados sugerem que a re-resolução de rotas ativa e baseada em evidências é uma alternativa viável ao planejamento exaustivo, oferecendo alta qualidade de rota com overhead computacional gerenciável.

Os autores observam limitações, incluindo a dependência da qualidade do prior de distância temporal aprendido e a avaliação atual em conjuntos de âncoras pequenos, sugerindo que escalar para conjuntos de waypoints maiores pode exigir poda mais forte e solucionadores combinatórios mais aproximados.